L_2_Zakony_logiki_ravnosilnye_preobrazovania_lektsia

Содержание

Слайд 2

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

Логическая равносильность, законы логики.
Равносильные преобразования в логике

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

Слайд 3

Логическая равносильность, законы логики.

Два высказывания равносильны, если они одновременно истинны или

Логическая равносильность, законы логики. Два высказывания равносильны, если они одновременно истинны или
одновременно ложны.
Две формулы равносильны если их эквиваленция является тавтологией (общезначима).
F1 ↔ F2 ≡ 1

Слайд 4

Логическая равносильность, законы логики.

Равносильность – это отношение между формулами и как отношение

Логическая равносильность, законы логики. Равносильность – это отношение между формулами и как
обладает свойствами рефлексивности, симметричности, транзинтивности.
Равносильности логики высказываний называют законами логики.
Основные законы логики и основные тавтологии: законы Аристотеля, де Моргана, идемпотентности.

Слайд 6

Логическая равносильность, законы логики.

Алгебра формул логики высказываний подобна алгебре множеств (законы коммутативности,

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

Слайд 7

Законы

Х ∨ УZ = (X ∨ У)(Х ∨ Z) – закон

Законы Х ∨ УZ = (X ∨ У)(Х ∨ Z) – закон
дистрибутивности дизъюнкции относительно конъюнкции.
X ∨ УХ = Х; Х(Х ∨ У) = Х – закон поглощения
ХУ ∨ ХУ = У; (Х ∨ У)(Х ∨ У) = Х – закон склеивания

Слайд 8

Если в равносильные формулы вместо какой-то переменной или подформулы подставить одну и

Если в равносильные формулы вместо какой-то переменной или подформулы подставить одну и
ту же формулу, то полученные формулы останутся равносильными. Это обозначается так:
(Х || У) или (Х,У) – «вместо Х подставить У».

Слайд 9

Принцип двойственности

Две формулы, не содержащие знаков импликации и эквиваленции называют двойственными,

Принцип двойственности Две формулы, не содержащие знаков импликации и эквиваленции называют двойственными,
если каждую из них можно получить из другой заменой символов конъюнкции, дизъюнкции, “0”, “1” на символы дизъюнкции, конъюнкции, “1”, “0”.
Принцип двойственности утверждает, что если две формулы равносильны, то и двойственные им формулы тоже равносильны.

Слайд 10

Дополнительные законы логики

PQ → P – “конъюнкция сильнее каждого из его

Дополнительные законы логики PQ → P – “конъюнкция сильнее каждого из его
членов.”
P → (P ∨ Q) – “дизъюнкция слабее каждого из её членов.”
P → (Q → P) – “истина из чего угодно.”
P → (P → Q) – “из ложного всё что угодно.”
“Перестановка посылок.” [P→ (Q → R)] ↔ [Q → (P → R)] – тавтология.
“Объединение и разъединение посылок.” [P → (Q → R)]↔[(PQ) → R]

Слайд 11

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

Замену одной формулы другой ей равносильной будем

Равносильные преобразования в логике высказываний Замену одной формулы другой ей равносильной будем
называть равносильным преобразованием данной формулы.
Упрощение формулы уменьшает число высказывательных переменных или знаков операций (минимизация).

Слайд 12

Формулы равносильных преобразований

Формулы равносильных преобразований

Слайд 13

Формулы равносильных преобразований

Формулы равносильных преобразований

Слайд 15

Преобразование форм представления формул логики высказываний

Скобочная форма, образуется непосредственно после формализации

Преобразование форм представления формул логики высказываний Скобочная форма, образуется непосредственно после формализации
высказывания
Дизъюнктивная нормальная форма (ДНФ) – дизъюнкция элементарных конъюнкций.
Конъюнктивная нормальная форма (КНФ) – конъюнкция элементарных дизъюнкций.
КНФ также называют клаузальная форма.

Слайд 16

Преобразование форм представления формул логики высказываний

Клауза – элементарная дизъюнкция.
Литера, литерал – элементарное

Преобразование форм представления формул логики высказываний Клауза – элементарная дизъюнкция. Литера, литерал
высказывание или его отрицание.
Дизъюнкт – дизъюнкция конечного числа литералов.
Хорновский дизъюнкт имеет не более одной не инверсной литеры.

Слайд 17

Пример:
Преобразование в КНФ обычно производится при помощи распределительного закона.
СКНФ получают из КНФ

Пример: Преобразование в КНФ обычно производится при помощи распределительного закона. СКНФ получают
путём добавления к каждому дизъюнту заведомо отрицательной литеры.

Слайд 18

Совершенная дизъюнктивная нормальная форма (СДНФ) – в каждой элементарной конъюнкции имеются все

Совершенная дизъюнктивная нормальная форма (СДНФ) – в каждой элементарной конъюнкции имеются все
n пропозициональных переменных.
Совершенная конъюнктивная нормальная форма (СКНФ) – в каждой элементарной дизъюнкции имеются все n пропозициональных переменных.

Слайд 19

Проблема дедукции в логике высказываний

В логике помимо равносильности широко используется относительные

Проблема дедукции в логике высказываний В логике помимо равносильности широко используется относительные
следования.
Формула S является следствием множества формул H (H├ S) если при всех интерпретациях, при которых истинны все формулы из H, истинна также и формула S.
Тавтология – следствие из пустого множества формул.

Слайд 20

S является следствием из H тогда и только тогда, когда H →

S является следствием из H тогда и только тогда, когда H →
S ≡ 1
(H├ S) ↔ (H → S) ≡ 1
├ (H → S) ≡ 1
(H1, H2, … , Hn) ├ S ↔ ├ (H1⋅ H2⋅ … ⋅ Hn) → S – импликация из конъюнкций этих формул тоже общезначима.

Слайд 21

Фундаментальная проблема логики: определить является ли S следствием из множества формул H

Фундаментальная проблема логики: определить является ли S следствием из множества формул H
(проблема дедукции).
Проблема описывается следующим выражением:
H∨S ≡ 0 (невыполнимо)
Имя файла: L_2_Zakony_logiki_ravnosilnye_preobrazovania_lektsia.pptx
Количество просмотров: 55
Количество скачиваний: 0