Логика высказываний

Логика высказываний

Простые высказывания – простые предложения, истинные или ложные по смыслу. Высказывания обозначаются буквами – А – атом (атомарная формула), которая может принимать значение «Истина» или «Ложь». Из простых высказываний можно составлять составные высказывания при помощи связок:

1).конъюнкция

А	В	А&В
И	И	И
И	Л	Л

2). дизъюнкция

А	В	А В
И	И	И
И	Л	И
Л	И	И
Л	Л	Л

3). отрицание

A	ùА
И	Л
Л	И

4). импликация А – посылка, В – следствие

А	В	А В
И	И	И
И	Л	Л
Л	И	И
Л	Л	И

5). эквивалентность (,~)

А	В	А ~ В
И	И	И
И	Л	И
Л	И	Л
Л	Л	Л

Определение. Правильная формула – это:

1) атомарная формула;

2)если G – формула, то ùG – тоже формула;

3) А&В, А + В, А®В, А ~ В – это формулы, если А и В – формулы;

4) повторное применение 2) и 3)

Определение.

1) если G и H – формулы, то формула ùG истинна, когда G – ложно;

2) G&H – истина тогда и только тогда, когда G и H – истинны;

3) GÚH – истина, если истинно хотя бы одно из высказываний, ложно, если оба ложны;

4) А®В,А – посылка, В – следствие; смысл – причинно-следственная связь,если посылка ложна, то следствие может быть любым;

5) А~В – истина тогда и только тогда, когда истинность А и В совпадает.

Связки: ~,®,Ú,&ù

Ранг связок – область действия связки.

min max

Скобки используются для обозначения области действия. Если область действия очевидна, их можно опускать.

(Q®(S&(AÚù(B))))=Q®S&(AÚùB)

Определение. Пусть задана формула G=G(A,B,C,D), где A,B,C,D – атомы.Подстановка конкретных высказываний (или просто их значений И или Л) называется интерпретацией.

При интерпретации составное высказывание также принимает значение И или Л, которое может быть определено по таблицам истинности.

Если в формуле n атомов, то таблица истинности содержит 2ⁿ переборов. Значение истинности определяется последовательно с учетом ранга связки.

Пример:ùАÚВ®С

А	В	С	ùА	ùАÚВ	ùАÚВ®С
Л	Л	Л	И	И	Л
Л	Л	И	И	И	И
Л	И	Л	И	И	И
Л	И	И	И	И	И
И	Л	Л	Л	Л	И
И	Л	И	Л	Л	Л
И	И	Л	Л	И	Л
И	И	И	Л	И	И

Для всевозможных интерпретаций всякая логическая формула является истинностной функцией, аргументами которой являются атомы и функция принимает значения «И» ил «Л».

Пользуясь таблицами истинности, функции разделяют на три класса:

1) тавтологии – формулы, истинные на всех наборах атомов (А®В)&А®В;

2) противоречия – формулы, ложные на всех наборах атомовА&ùА;

3) случайные (выполнимые) – существует интерпретация, при которой формула истинна:

а) если формула F истинна в интерпретации I, то F выполнима в I, при этом I – модель F;

б) если формула F ложна в I, то F опровергается в I.

Теорема 1: Если формула В – тавтология и формула В^*, полученная из В при подстановке формулы А вместо любого вхождения символа В, то формула В^* - тоже тавтология.

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

Пример:

А®ВÚА

А=СÚP&B

(CÚP&B)®BÚ(CÚP&B)

«Проблема разрешимости» - существует ли метод или алгоритм. Который позволяет за конечное число шагов определить, является ли формула тавтологией. Она решается положительно методом таблиц истинности.

1.2 Алгебра логики

Определение. Две формулы А(x₁,…x_n) и В(x₁,…x_n), где x₁,…x_n – атомы, простые выражения, называются равносильными (тождественно равными, «º»), если при любых интерпретациях значения истинности совпадают. В этом случае мы пишем

А(x₁,…x_n)ºВ(x₁,…x_n).

Утверждение: А тождественно равно В, если А~В – тавтология.

Законы логики формулируются в виде тождеств.

Законы логики:

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

a&b=b&a

aÚb=bÚa

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

a&(b&c)=(a&b)&c

aÚ(bÚc)=(aÚb)Úc

3) идемпотентность

aÚa=a a&a=a

4) дистрибутивность

a&(bÚc)=(a&b)Ú(a&c)

aÚ(b&c)=(aÚb)&(aÚc)

5) двойное отрицание

ù(ùa)=a

6) правила де Моргана

ù(aÚb)=ùa&ùb

ù(a&b)=ùaÚùb

7) замена импликации

a®b=ùaÚb

8) закон контрапозиции

(a®b)=(ùb®ùa)

9)

(a®c)&(b®c)=(aÚb)®c

(a®b)&(a®c)=a®(b&c)

10) метод доказательства необходимости и достаточности

a~b=(a®b)&(b®a)

11)законы сокращения

aÚ(ùa&b)=aÚb

a&(ùaÚb)=a&b

Теорема 1: Пусть С_А – формула, в которой выделена формула А, в результате замены формулы А на формулу В получим формулу С_В, тогда:

1) С_В – тавтология, если С_А – тавтология;

2) С_А=С_В, если А=В

Обозначим множество всех высказываний S={a,b,c…},очевидно, что отрицание этих высказываний тоже входит в это множество. Дополним множество двумя константами: «И»(1) и «Л»(0).

На множестве S определены операции &,Ú, которые удовлетворяют перечисленным ранее законам. На этом множестве справедливы также законы нулевого, единичного и дополнительного элементов:

0Úа=а 1Úа=1 аÚùа=1

0&а=0 1&а=а а&ùа=0

Алгебра логики, удовлетворяющая этим свойствам, называется булевой алгеброй.

Примеры:

1).Рассуждение 1: Студент пойдет домой или останется в институте.

Рассуждение 2: Студент не останется в институте, следовательно, он пойдет домой.

2). Рассуждение 1: Студент пойдет домой или останется в институте.

Рассуждение 2: Студент останется в институте, следовательно, он не пойдет домой.

(aÚb)&b®ùa

-не тавтология

Используется неправильная связка(во втором примере, первом предложении), надо: студент либо останется в институте, либо пойдет домой, тогда:

(А+В)&В®ùА

-тавтология.

Определение. Литера – это атом или его отрицание.

Определение. Формула F находится в конъюнктивной нормальной форме (КНФ), где F_i – дизъюнкция литер – дизъюнктер.

F=F₁&F₂&…&F_k

Пример: F=(aÚb)&(aÚbÚùc)

Определение. Формула F представлена в дизъюнктивной нормальной форме (ДНФ), если F_i– конъюнкция литер – конъюнктер, терм.

F=F₁ Ú F₂ Ú F_k

Пример: F=(a&b)Ú(ùa&b&c)

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

Алгоритм преобразования:

1) заменить все связки ®,~ формулами, содержащими ù,Ú,&;

2) применяя правило де Моргана, привести все инверсии к атомам;

3) исключить промежуточные скобки с применением дистрибутивных законов.

Пример: (a ® (b ® c))®ùb

(a®(`b Ú c)) ®`b

(`a Ú`b Ú c) ®`b

a × b ×`c Ú`b

a ×`c Ú`b

(a Ú`b)×(`c Ú`b) - КНФ

Методы правильных рассуждений:

1).Закон контрапозиции (доказательство от противного):

(p®q)@(ùq®ùp) - тождество

предполагается что не q, доказывается, что не p Þ приходим к противоречию. Доказательство, что если ùq, то ùp Þпротиворечие

Если ùp – ложно, то p – истина.

(`p Ú q)=(q Ú`p) – тавтология

2).Закон косвенного доказательства:

(ùp®q)&(ùp®ùq)®p

q,ùq – противоречие, следовательно, p – истина.

3).Доказательство разбором случаев:

(pÚq)&(p®r)&(q®r)®r:

Нужно доказать r

Разбираются возможные случаи: доказывается, что p®r и q®r. Отсюда следует, что r – истина.

4).Доказательство цепочкой импликаций (свойство транзитивности импликаций):

(p®q)&(q®r)®(p®r)

Требуется доказать, что (p®r). Выбирается промежуточное утверждение q и последовательно доказывается (p®q), потом (q®r). Затем вывод (p®r).

1.3 Исчисление высказываний – формальная аксиоматическая теория.

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

В математической теории истинные высказывания называются доказуемыми или теоремами. Теоремы выводятся из некоторых фиксированных заранее высказываний, которые называются аксиомами.

Определение. Формальное доказательство – последовательность высказываний или теорем, каждая из которых либо аксиома, либо подстановка в аксиому, либо выводится логически по правилам вывода. Последнее высказывание и есть теорема.

Логика высказываний является аксиоматической теорией. Теоремами являются тавтологии.

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