матлогика - шпора

30. Доказательство логических выражений с использованием таблиц истинности.

В правильности результата можно убедится с помощью таблицы истинности.

31. Способы доказательства логических выражений с использованием специальных приемов.

Способ доказательства с использованием раскрытия Булевых операций их из определения и некоторых законов логики Буля.

1 пример. Доказать тождество

(a∩b∩c)→(a U b U c)=(a→b) U (b→c) U (c→a)

Доказательство: (a∩b∩c)→(a U b U c)=по определению операции импликации = (a b c) (a b c) = по закону де Моргана =

((a b c) a b c) (a b) (b c) (c a) = по определению импликации =

(a b) (b c) (c a) ; a (b c) a | (b | c)

Доказательство: a (b c) a (b c) a (b | c) a (b | c) a | (b | c)

Доказательство специального характера Доказать, что A B 1, если A B Доказательство:

A B A (A B) A A B 1 B 1

Доказательство и использованием ―Умножения‖ слева и справа. На дополнительную импликанту.

Доказать закон де Моргана

(a b) a b

умножим слева на (a U b):

(a b) (a b) 0

умножим справа (a U b):

(a b) (a b) (a a) (b b) 0 0 0

32. Логика высказываний и операции логики высказываний.

Высказывание – грамматически правильное предложение, про которое можно сказать истинно оно или ложно. ПРИМЕР : «Киев – столица Украины» (И) – истинна «Томск – столица Японии» (Λ) ложь Пусть имеем два след. Высказывания: А = «на улице идет дождь» В = «над головой раскрыт. зонт»

С помощью логических связок можно образовать более сложное высказывание - отрицание Ā = «на улице не идет дождь»; - дизъюнкция Ā U В = «на улице не идет дождь или/и над головой раскрыт зонт»; - конъюнкция А В = «На улице идет дождь и над головой не раскрыт зонт»; - импликация А → В «Если на улице идет дождь, то над головой раскрыт зонт»; - эквивалентность В ~ А = «Над головой раскрыт зонт, тогда и только тогда, когда идет дождь» Другие

логические связи в логике высказываний не используются. РАССМОТРИМ ПОДРОБНО:

1.ОТРИЦАНИЕ Ā. Высказывание А по другому можно прочитать так: « истинно то, что на улице идет дождь » Если А = 0, то это означает, что на улице нет дождя. Дополнение к А : Ā также отрицательно на истинное высказывание: «истинно то, что на улице не идет дождь» Тогда: Ā = 1 (отсутствие дождя)( А = 0

)

2.ДИЗЪЮНКЦИЯ В общем случае подразумевают так же конъюнкцию двух высказываний. Т. е. обознач. « или » однако часто возникает необходимость обязать высказывание только союзом «или»

ПРИМЕР: Р=«Петр находится в бассейне» Q=«Петр находится в театре»PVQ=«Петр находится в бассейне или в театре ». Если необходимо точно показать где находится Петр, то нужно записать, (P V Q)Λ( PVQ ) = (P V

Q)Λ( PVQ ). C точки зрения логики Буля эта операция соответствует ассиметричной разности P + Q , + - не используется => необходимо применить запись показанную выше.

обязательно должен представляться через грамматический союз «И», например - А Λ B = « На улице идет дождь, а над головой не раскрыт зонт » Может возникнуть такая семантическая ситуация, тогда союз «И» не выполнят роль конъюнкции. ПРИМЕР: С = «Ему стало грустно и он прибил таракана тапочком», D=«он прибил таракана тапочком и ему стало грустно » В этих двух предложениях конъюкция неочевидна. Различие двух высказываний очевидно и мы имеем дело со скрытой импликацией,т.е.следствие(одно простое выражение обуславливает уравнение)

4.ИМПЛИКАЦИЯ. Высказывания типа «если А,то В» имеют объясняющий характер(причина-следствие). Т. е. что имеет место событие В, потому, что произошло событие А.

Грамматически импликация может быть оформлена:«А является достаточным основанием для В»; «В потому,что А»;«В при условии выполнения А» и т.п. ~ причинно – следствие отношения можно записывать в виде таблицы истинности.

Даная таблица является таблицей истинности для импликации, как в логике Буля, так и в логике высказывания.

5.ЭКВИВАЛЕНТНОСТЬ. Может интерпретироваться высказываниями «А эквивалентно В»,а также «А равно В»,«А тождественно В»,«А равносильно

В»,«А тогда и только тогда В»и т.п. Экв-ность выражается через конъюнкцию двух импликацийA~В=(А→В)Λ(В→А), такое отношение часто возникает при одновременном высказывании 2-х условий «из А следует В» и «из В следует А».=>при эквивалентности нельзя одному событию принимать только роль причину, а другому только следствие и наоборот. ПРИМЕР: R=«нарастание анархии в обществе», S=«падение авторитета власти».Это события являются разнопорядковыми, т.к. R происходит из-за S и наоборот S происходит из-за R, R и S образую здесь логический круг кот-ый называется СИЛЬНОСВЯЗАННЫМ и выражают следующими множествами R~S=(RΛS)~(RVS ) или l=(RVS)→(RΛS). Понятие сильной связанности совпадают с понятием экви-ти если речь идет о двух событиях.

33. Таблицы истинности операций логики высказываний.

1. Отрицание:

А = «На улице идет дождь», А = «На улице не идет дождь»

дизъюнкция Ā U В = «на улице не идет дождь или/и над головой раскрыт зонт»

3. Конъюнкция:

конъюнкция А ∩ В = «На улице идет дождь и над головой раскрыт зонт»

4. Импликация:

импликация А → В «Если на улице идет дождь, то над головой раскрыт зонт »

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

« А эквивалентно В »

34. Различия логики Буля и логики высказываний.

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

2-е логические функции в логике Буля считаются эквивалентными, если они на одинаковых полных наборов 0 и 1, для соответствующих аргументов дают абсолютно одинаковые значение 0 и 1 для двух сравниваемых функций.

Все звенья доказательств в логике Буля связывают со знаком равенства. Отношение эквивалентности удовлетворяет 3 законам, которые используются в логике высказываний.

1) рефлективности А=А 2) симметричности: если А=В, то В=А

3) транзитивности: если А=В и В=С, то А=С

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

Отдельные звенья доказательств связываются не знаком ―=‖, а знаком импликации, при этом символ импликации ―→‖ заменяется в доказательстве логики высказываний на ―=>‖

Влогике высказываний следует различать:

1)объектные высказывания

2)субъектные высказывания

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

36. Аксиомы, противоречия и тавтологии в логике высказываний.

Если символ метода эмпликации клаузы P1,P2,…,Pn-1=> ;C (2.2) сместить в крайнее левое положение ,то клауза превратится в тафталогию:

n-1,Pn

Для доказательства логических клауз используются методы 1)аксоматический (аксиоматический подход к док-ву логич. Высказываний 2)метод таблицы истинности (конструктивный подход)

3)метод резолюции

4)метод Вонга

5)метод натурального исчисления Аксоматический метод основан на независимой системы аксиом с помощью

которых можно установить истинность или ложность любой клауз :

1)1=>A(BA)

2)1=>(A(BC))((AB)(AC))

3)1=>(A(BC))(B(AC))

Данная аксиома отображает:

1)закон отношения порядка

2)закон коммутативности

3)закон ассоциативности

4)закон дистрибутивности

5)закон двойного отрицания (0 и 1)

Доказательство при аксиоматическом подходе сводится к таким эквивалентным преобразованиям логических выражений, с помощью обозначенных выше аксиом, которые приводят к выполнению или не выполнению основной аксиомы логических высказываний, отображающей отношение порядка, и которое может быть представлена в общем случае следующим образом: А,ВA ,что можно выразить так: если раньше было установлена, что А истинно, то истинность В не повлияет так, что А станет ложным

37. Конструктивный подход к доказательству логических выражений в логике высказываний.

Конструктивный подход доказательства логических высказываний с помощью таблицы истинности.

Для этого составим таблицу истинности для следующего примера: Пусть дана легенда: «Кассир сидорова сказала, что она видела грузчика

Иванова в комнате отдыха. Эта комната имеет тонкую перегородку и находится рядом со складом готовой продукции. Стреляли. Грузчик сказал, что никаких выстрелов не слышал» Вывод исследователя: «если кассир говорит правду, то грузчик вводит

следствие в заблуждение, не могут кассир и грузчик одновременно говорить правду»

Введем обозначение для высказываний:

А= ―Кассир сказала правду‖; В= ―Грузчик находился в комнате отдыха‖;

С= ―Комната отдыха находится рядом со складом‖; D= ―грузчик слышал выстрелы‖;

Е= ―грузчик говорит правду‖;

Исходные посылки следователя:

Р1 = А→В = если А, то В; Р2 = В→С = если В то С; Р3 = С→D = если С то D;

Р4=Е→ D =если Е, то не D= если верит грузчику, то он не слышал выстрелов.

Заключение следователя (что ему нужно проверить):

С1=А→ Е (грузчик обманывает, если кассир сказала правду); С2=А∩Е (кассир и грузчик одновременно говорят правду)

Формальная запись легенды:

А→В, В→С, С→D, Е→ D => С1; С2

Составим таблицу истинности:

Сначала обозначим обобщенную посылку Р=Р1 ∩Р2 ∩Р3 ∩Р4

Клауза считается истинной если все единицы следствия накрывают все единицы обобщенной причины Р. Т.е. единицы обобщенной причины образуют подмножество единиц следствия.Для С1, Р=(0,8,12,14,15,16)

(0,1,2,..,16,18,20)=С1

Следовательно заключение является истинным для С2.Р=(0,8,12,14,15,16) {17,19,21,…,31}=С2

Следовательно заключение С2 ложно. С помощью таблицы истинности не

трудно установить истинность тавтологии1=> Ð , Ð , Ð , Ð ;Ñ а также

1 2 3 4 1

справедливость противоречияР1, Р2, Р3, Р4, C1 =>0.