Презентация "Основы логики. Алгебра высказываний" 10-11 класс

Основы логики

• Алгебра высказываний
• Автор:
• Сергеев Евгений Викторович
• МОУ СОШ №4 г. Миньяра Челябинской области
• [email protected]
• http://shk4-minyar.ucoz.ru

Алгебра высказываний

• Алгебра высказываний была разработана для того, чтобы определять истинность или ложность составных высказываний, не вникая в их содержание

Логические переменные

• Логические переменные – простые высказывания, содержащие только одну мысль.
• Обозначаются буквами латинского алфавита: A, B, C…
• Логические переменные могут принимать лишь два значения: «ИСТИНА» (1) или «ЛОЖЬ» (0)

Логические переменные

• Например, два простых высказывания:
• А = «2  2 = 4» истина (1)
• В = «2  2 = 5» ложь (0)
• являются логическими переменными А и В

• В алгебре высказываний высказывания обозначаются именами логических переменных, которые могут принимать лишь два значения: «ИСТИНА» (1) или «ЛОЖЬ» (0)

• В алгебре высказываний над логическими переменными (над высказываниями) можно производить определенные логические операции, в результате которых получаются новые высказывания

Составные высказывания

• Высказывания, состоящие из нескольких простых суждений и содержащие в себе более, чем одну простую мысль, называются логическими функциями
• Обозначаются F(A,B,C…)
• Также могут принимать значения «ИСТИНА» или «ЛОЖЬ» в зависимости от того, какие значения имеют входящие в их состав логические переменные и от действий над ними

Логические операции

• Конъюнкция (логическое умножение, «И»)
• Дизъюнкция (логическое сложение, «ИЛИ»)
• Инверсия (логическое отрицание, «НЕ»)
• Импликация (логическое следование, «Если А, то В»)
• Эквивалентность (логическое равенство, «А тогда и только тогда, когда В»)

• Объединение двух или нескольких высказываний в одно с помощью союза «И» называется операцией логического умножения, или конъюнкцией

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

Конъюнкция. Определите истинность логической функции

• «2  2 = 5» И «3  3 = 10»
• «2  2 = 5» И «3  3 = 9»
• «2  2 = 4» И «3  3 = 10»
• «2  2 = 4» И «3  3 = 9»
• Истинна только функция (4)

Запись конъюнкции на формальном языке алгебры высказываний

• F(A,B) = A & B
• или
• F(A,B) = A  B
• Также может встретиться запись, типа:
• F(A,B) = A * B
• или
• F(A,B) = A and B

Значение логической функции определяется по ее таблице истинности

• Таблица истинности показывает какие значения принимает логическая функция при всех возможных значениях логических переменных

Таблица истинности для конъюнкции

A	B	A  B
2  2 = 5	3  3 = 10	ЛОЖЬ
2  2 = 5	3  3 = 9	ЛОЖЬ
2  2 = 4	3  3 = 10	ЛОЖЬ
2  2 = 4	3  3 = 9	ИСТИНА

Таблица истинности для конъюнкции

A	B	A  B
0	0	0
0	1	0
1	0	0
1	1	1

• Объединение двух или нескольких высказываний в одно с помощью союза «ИЛИ» называется операцией логического сложения, или дизъюнкцией

• Логическая функция, полученная в результате дизъюнкции, истинна тогда, когда истинна хотя бы одна из входящих в него логических переменных

Дизъюнкция. Определите истинность логической функции

• «2  2 = 5» ИЛИ «3  3 = 10»
• «2  2 = 5» ИЛИ «3  3 = 9»
• «2  2 = 4» ИЛИ «3  3 = 10»
• «2  2 = 4» ИЛИ «3  3 = 9»
• Ложна только функция (1), остальные истинны

Запись дизъюнкции на формальном языке алгебры высказываний

• F(A,B) = A  B
• Также может встретиться запись, типа:
• F(A,B) = A + B
• или
• F(A,B) = A or B

Таблица истинности для дизъюнкции

A	B	A  B
2  2 = 5	3  3 = 10	ЛОЖЬ
2  2 = 5	3  3 = 9	ИСТИНА
2  2 = 4	3  3 = 10	ИСТИНА
2  2 = 4	3  3 = 9	ИСТИНА

Таблица истинности для дизъюнкции

A	B	A  B
0	0	0
0	1	1
1	0	1
1	1	1

• Присоединение частицы «НЕ» к высказыванию называется операцией логического отрицания, или инверсией

• Логическое отрицание (инверсия) делает истинное высказывание ложным, а ложное – истинным [логическая отрицательная единица, перевертыш]

Инверсия

• Пусть
• A = «2  2 = 4»
• – истинное высказывание, тогда
• F(A) = «2  2 ≠ 4»
• – ложное высказывание

Запись инверсии на формальном языке алгебры высказываний

• F(A) = ¬A
• или
• F(A) = Ā
• Также может встретиться запись, типа:
• F(A) = not А

Таблица истинности для инверсии

А	¬А
0	1
1	0

Таблицы истинности основных логических функций

• Логическое умножение

• A
• 0
• 0
• 1
• 1

• B
• 0
• 1
• 0
• 1

• A  B
• 0
• 0
• 0
• 1

• Логическое сложение

• Логическое отрицание

• A
• 0
• 1

• ¬A
• 1
• 0

• A
• 0
• 0
• 1
• 1

• B
• 0
• 1
• 0
• 1

• А  В
• 0
• 1
• 1
• 1

Дополнительные логические функции

• Импликацию и эквивалентность можно выразить через конъюнкцию, дизъюнкцию и отрицание, поэтому их называют дополнительными логическими функциями:
• Импликация:
• А → В = ¬A  В или
• А  В = ¬A  В или
• А  В = ¬A  В
• Эквивалентность:
• А ↔ В = (¬A  В)  (¬B  A) или
• А  В = (¬A  В)  (¬B  A) или
• А ≡ В = (¬A  В)  (¬B  A)

Импликация

• Объединение двух высказываний, из которых первое является условием, а второе – следствием из него, называется импликацией (логическим следованием)

Импликация

• Импликация ложна тогда и только тогда, когда условие истинно, а следствие ложно
• Пример:
• Если выучишь материал, то сдашь зачет
• Это высказывание ложно только тогда, когда материал выучен, а зачет не сдан, т.к. сдать зачет можно и случайно, например если попался единственный знакомый вопрос или удалось воспользоваться шпаргалкой

Таблица истинности для импликации

A	B	A → B
0	0	1
0	1	1
1	0	0
1	1	1

Эквивалентность

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

Таблица истинности для эквивалентности

A	B	A  B
0	0	1
0	1	0
1	0	0
1	1	1

Переместительный

• Дизъюнкция:
• X  Y ≡ Y  X
• Конъюнкция:
• X  Y ≡ Y  X

• Основные законы алгебры высказываний

Сочетательный

• Дизъюнкция:
• X  (Y  Z) ≡ (X  Y)  Z
• Конъюнкция:
• X  (Y  Z) ≡ (X  Y)  Z

• Основные законы алгебры высказываний

Распределительный

• Дизъюнкция:
• X  (Y  Z) ≡ X  Y  X  Z
• Конъюнкция:
• X  (Y  Z) ≡ (X  Y)  (X  Z)

• Основные законы алгебры высказываний

Правила де Моргана

• Дизъюнкция:
• ¬(X  Y) ≡ ¬X  ¬Y
• Конъюнкция:
• ¬(X  Y) ≡ ¬X  ¬Y

• Основные законы алгебры высказываний

Идемпотенции

• Дизъюнкция:
• X  X ≡ X
• Конъюнкция:
• X  X ≡ X

• Основные законы алгебры высказываний

Поглощения

• Дизъюнкция:
• X  (X  Y) ≡ X
• Конъюнкция:
• X  (X  Y) ≡ X

• Основные законы алгебры высказываний

Склеивания

• Дизъюнкция:
• (X  Y)  (¬X  Y) ≡ Y
• Конъюнкция:
• (X  Y)  (¬X  Y) ≡ Y

• Основные законы алгебры высказываний

Переменная со своей инверсией

• Дизъюнкция:
• X  ¬X ≡ 1
• Конъюнкция:
• X  ¬X ≡ 0

• Основные законы алгебры высказываний

Операция с константами

• Дизъюнкция:
• X  0 ≡ X, X  1 ≡ 1
• Конъюнкция:
• X  0 ≡ 0, X  1 ≡ X

• Основные законы алгебры высказываний

Двойного отрицания

• ¬(¬X) ≡ X

• Основные законы алгебры высказываний

Порядок действий

• Действия в скобках
• Отрицание
• Конъюнкция
• Дизъюнкция
• Импликация
• Эквивалентность