Презентация, доклад на тему Логические основы построения компьютера

и сложные
Логические выражения и логические операции
Законы алгебры логики

Серебренникова Н.В. учитель информатики МАОУ СОШ №35 г.Улан-Удэ

процесс мышления.
Основными формами мышления являются:

Понятие

Суждение

Умозаключение

это форма мышления, которая выделяет существенные признаки предмета или класса предметов, отличающие его от других (например: человек, компьютер).

это мысль, в которой что-то утверждается или отрицается о предметах (например: «дважды два равно четыре»).

это приём мышления, позволяющий на основе одного или нескольких суждений-посылок получить новое суждение (знание или вывод) (например: доказательства теорем в геометрии).

воспитатель Александра Македонского) впервые разработал научную систему логики, заложил основы формальной логики.
XVII в. Великий немецкий учёный Готфрид Вильгельм Лейбниц попытался перевести формальную логику из словесного царства в царство математики.
XVIII в. Великий английский математик Джордж Буль изобрёл своеобразную алгебру (алгебра Буля или булева алгебра)– систему обозначений и правил, применяемую к всевозможным объектам.
Современный вид математическая логика приобрела в 1880-е годы в трудах немецкого логика, математика и философа Готлоба Фреге. Он ввёл впервые аксиомы логики высказываний и предикатов и сделал попытку свести математику к логике.

Изучает вопросы применения математических методов для решения логических задач и построения логических схем, которые лежат в основе работы компьютера.

Алгебра высказываний (алгебра логики, алгебра Буля, булева алгебра) - раздел математической логики, занимающийся обработкой логических выражений.

Суждения

Высказывания

Логические
выражения

или

предложение, о котором всегда можно сказать, истинно оно или ложно.

Например:
«Каждый ромб параллелограмм»
«Каждый параллелограмм – ромб»

Сложное (составное) высказывание получается из простых высказываний с использованием союзов-связок «И», «ИЛИ» и частицы «НЕ». Простые или сложные высказывания называют логическими выражениями.

- это символическая запись, состоящая из логических величин (констант и переменных), объединённых логическими операциями.

Обозначаются логические переменные буквами латинского алфавита (А, В, …), которые могут принимать два значения: ИСТИНА или ЛОЖЬ.

основные логические операции.
Дополнительные операции – импликация, эквивалентность и исключающая дизъюнкция.

Пусть А и В – некоторые произвольные высказывания. Рассмотрим таблицу логических операций над этими высказываниями:

«На улице светит солнце»
B - «На улице пасмурная погода»

отрицание.

¬ А
Результат инверсии ложь(0), если исходное выражение истинно(1), и наоборот, результат истина(1), если исходное ложь(0).

Пример: «Петя будет дежурным» - А «Петя не будет дежурным» - «Трижды три равно семи» - В «Неверно, что трижды три равно семи» -

умножение.

(А&В или АВ или AxB)
Результат конъюнкции истина (1), когда оба выражения истина (1).

Пример:
«K – чётное число» - А
«K – делится на три» - В.
Чему равен результат логического умножения А&В?

умножение.

Решение:
Множество всех случаев, когда А истина:
К = 2, 4, 6, 8, 10, 12, 14, 16, 18…
Множество всех случаев, когда В истина:
К = 3, 6, 9, 12, 15, 18…
Множество всех случаев, когда истина А&В:
К = 6, 12, 18…

А&B

А

В

сложение.

( А+В )
Результат дизъюнкции истина (1), когда истино (1) хотя бы одно из исходных высказываний.

Пример:
«К – чётное число» - А
«К – делится на три» - В.
Чему равен результат логического сложения А ∨ В ?

сложение.

Решение:
Множество всех случаев, когда А истина:
К = 2, 4, 6, 8, 10, 12…
Множество всех случаев, когда В истина:
К = 3, 6, 9, 12, …
Множество всех случаев, когда истина А∨В:
К = 2, 3, 4, 6, 8, 9…

А∨В

- логическое следование.

Результат импликации ложь (0), когда условие истинно (1), а следствие ложно (0).

Пример:
«К – делится на 9» - А
«К – делится на 3» - В
Операция А→В означает: «Если число делится на 9, то оно делится и на 3».

- логическое следование.

а) А – ложно, В – ложно.
б) А – ложно, В – истина.
в) А – истина, В – истина.
г) А –истина, В – ложно
К= нет таких чисел.

К={4,17,22…}

К={6,12,21…}

К={9,18,27…}

ТОГДА, КОГДА» - равнозначность.

А~В или А≡В
Результат эквивалентности истина (1), когда оба исходных выражения одновременно истинны (1) или ложны (0).

Пример: Высказывание А: «сумма цифр, составляющих число К, делится на 3»; высказывание В: «К – делится на 3».

Операция А↔В означает: «число делится на 3 тогда и только тогда, когда сумма его цифр делится на 3».

- неэквивалентность.

Результат неэквивалентности истина (1), когда одно из исходных выражений истина (1), другое ложь (0).

Пример: Высказывание: «За контрольную работу мне поставят 4 или 5» истинно, т.к. одновременно 4 и 5 за контрольную получить нельзя.

«Июнь месяц я проведу в деревне или в пионерском лагере». Союз ИЛИ подчёркивает мысль, что можно быть либо в деревне, либо в лагере, но никак не в обоих местах одновременно.

знания или везение» ? Какой операции равносильно это высказывание?
Один зажиточный человек очень боялся грабителей и заказал замок, который открывался двумя ключами одновременно. С какой логической операцией можно сравнить процесс открывания?

А: «Утки зимуют на юге»
В: «Лето утки проводят на севере»
С: «Утки не совершают перелётов»
Приведите пример высказывания, соответствующий логической операции – импликация.
Приведите пример высказывания, соответствующий логической операции – эквивалентность.

с учётом скобок слева направо:

Для изменения порядка используются круглые скобки.

или в трамвае и почитаю по дороге книгу».
Решение: Данное высказывание создано из трёх простых высказываний :
А: «Я поеду в автобусе»
В: «Я поеду в трамвае»
С: «По дороге я почитаю книгу»
А и В образуют логическую сумму: А∨ В
Сумма (А∨ В) вместе с высказыванием С образуют логическое произведение: (А∨ В)∧ С

«Петя едет в автобусе»
В: «Петя читает книгу»
С: «Петя насвистывает»
Расшифровать выражения:
а) Х = ¬А ∧ В ∧ ¬С б) Х = ¬(А∧В)

«Петя не едет в автобусе и, не насвистывая, читает книгу»

«Неверно, что Петя едет в автобусе и насвистывает»

и, если ему повезёт, он вернётся домой с уловом».
Решение: Данное высказывание создано из трёх простых высказываний :
А: «Вася пойдёт на рыбалку»
В: «Ему повезёт»
С: «Он вернётся домой с уловом»
В и С образуют импликацию: В → С
Импликация (В →С) вместе с высказыванием А образуют конъюнкцию: А ∧ (В→С)

ветер, то солнце светит лишь тогда, когда нет дождя».
Решение: Высказывание разобьём на три простых:
А: «Дует ветер»
В: «Солнце светит»
С: «Дождь идёт»
В и ¬С образуют эквивалентность: В ↔ ¬ С
Высказывание А с эквивалентностью (В ↔¬С) образуют импликацию: А → (В↔¬С)
Результат:

булевой алгебры, позволяющие производить тождественные преобразования логических выражений:
Закон идемпотентности (отсутствие степеней и коэффициентов): А & A = A A ∨ A = A
Закон коммутативности (переместительный): A ∨ B = B∨ A A & B = B & A
Закон ассоциативности (сочетательный): (A∨ B)∨ C = A∨ (B ∨ C) (A & B) & C = A & (B & C )
Законы дистрибутивности (распределительные): (A∨ B) & C = (A & C)∨ (B & C) (A & B)∨ C = (A∨ C)&(B∨ C)
Законы де Моргана: первый – A & B = A∨ B
второй – A∨ B = A & B

7. Закон исключения третьего (тождественно-истинное высказыва-ние): A ∨ А = 1 (всегда истина)
8. Закон противоречия (тождественное высказывание): A & А = 0 (всегда ложь )
9. Действия с логическими константами: A∨ 1 = 1 (всегда истина) А & 1 = A А∨ 0 = А А & 0 = 0 (всегда ложь)

Следствие основных законов:
Формулы поглощения: А ∨ А & В = A A & (A ∨ B) = A
А ∨ (А & В) = A ∨ B A & (A ∨ B) = A & B
2. Формулы склеивания: A & B∨ A & B = A (A∨ B) & (A∨ B) = A
3. Формулы замены операций: A ↔ B = A & B∨ A & B
A ↔ B = (A∨ B) & (A ∨ B)
A ↔ B = (A→B) & (B→A )
A→B = ¬A∨ B