Презентация на тему Логика высказываний

исчисления, в основные понятия которых входят такие понятия как

формальный язык исчисления, аксиомы исчисления и правила вывода.
Исчисления высказываний
Исчисление предикатов
Теория алгоритмов
Сложность алгоритмов
Многозначная логика

которого можно сказать истинно оно или ложно.
Определение. Истинностным значением

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

В – атомарные (пропозициональные) высказывания, тогда из них можно

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

множество. Элементы алфавита – символы.
Определение. Слово – произвольная последовательность

символов (возможно пустая).
Определение. Произведением слов А и В в некотором алфавите называется слово АВ.
Определение. Слово В называется подсловом слова А, если существуют такие слова А1 и А2, такие что А=А1 В А2
Определение. Говорят, что слово С получено из слова А подстановкой слова D вместо подслова В, если А=А1 В А2 и С=А1 D A2 .
Определение. Говорят, что слово С получено из слова А путем замены символа v на слово B, если в слове вместо всех символов v подставлено слово B.

высказываний. Элементы этого множества можно разбить на следующие 3

группы:

именные символы
логические символы
служебные символы

P, Q, P1, Q1,
,,,,~.
открывающиеся ( и закрывающиеся ) скобки

Определение. Формулой алгебры высказываний называется:
1. Высказывательная (пропозициональная) переменная
2. Если и некоторые формулы, то
тоже являются формулами.
3. Других формул, кроме перечисленных в пунктах (1) и (2), нет.
 

Х1,…,Хn - высказывательные переменные, входящие в формулу A.
Определение.

Интерпретацией формулы A называется любой конкретный набор истинностных значений, приписанных переменным Х1,…,Хn.
Пусть I – некоторая интерпретация (т.е. набор значений переменных Х1,…,Хn). Тогда через I(A) обозначается значение формулы A в интерпретации I. Формулами, имеющими наиболее простую интерпретацию, являются формулы, равные И либо Л при любой интерпретации.
Определение. Формула называется выполнимой, если она истинна хотя бы при одной интерпретации.
Определение. Формула, истинная при всех возможных интерпретациях, называется общезначимой или тавтологией.
Определение. Формула, ложная при всех возможных интерпретациях, называется невыполнимой или противоречием.
Определение. Формула называется опровержимой, если при некоторой интерпретации она принимает значение Л.

позволяет выполнять равносильные преобразования формул для их упрощения или

приведения к специальной форме. Например для доказательства того, что формула является тавтологией нужно равносильными преобразованиями свести ее к формуле, очевидно являющейся тавтологией. Правило замены: если
F(A1, A2, ... , An) = G(A1, A2, ... , An), то для любой формулы алгебры высказываний
H(X1, X2, ... , Xi-1, Xi, Xi+1, ... , Xm) имеет место равносильность
H(X1, X2, ... , Xi-1, F(A1, A2, ... , An), Xi+1, ... , Xm) = H(X1, X2, ... , Xi-1, G(A1, A2, ... , An), Xi+1, ... , Xm)
 
2 правило. Правило заключения основано на применении теоремы 1.2.
Теорема 1.2: Если формулы A и AB – тавтологии, то B – тавтология.
Доказательство: Предположим противное, т.е. для некоторой интерпретации I имеем I(B)=Л. I(A)=И, т.к. A – тавтология, то I(AB)=Л, что противоречит тому, что AB – тавтология.
 
3 правило. Правило подстановки: если формула F, содержащая атом A, является тавтологией, то подстановка в формулу F вместо A любой формулы H снова приведет к тавтологии.

и B, зависящие от одного и того же набора

высказывательных переменных называются равносильными, если I(A)=I(B) для любой интерпретации I. Равносильность формул A и B записывается следующим образом:AB.
Определение. Формула B логически следует из формулы A (обозначается AB), если формула B имеет значение И при всех интерпретациях, при которых формула A имеет значение И.

Отношение равносильности на множестве формул логики высказываний является отношением эквивалентности, так как оно:
Рефлексивно AA
Симметрично AB  ВА
Транзитивно AB и ВС  АС

вариантов значений
Пусть для некоторой интерпретации I имеем:
I((AB))=И

I(AB)=Л  I(A)=Л и I(B)=Л  I(A)=И и I(B)=И  I(AB)=И.
Случай I((AB))=Л рассматривается аналогично.
Обратно, пусть I(AB)=И  I(A)=И и I(B)=И  I(A)=Л, I(B)=Л  I(AB)=Л  I((AB))=И.

1.3. Пусть AB и C – произвольная формула. Тогда:
A=B
AC=BC;

CA=CB
AC=BC; CA=CB
ACBC; CACB
A~CB~C; C~AC~B

Доказательство: продемонстрируем на примере одного из соотношений. Пусть при некоторой интерпретации I имеем I(A)=I(B)=s; и пусть I(C)=t. Тогда обе части каждой из формул, например, 4) ACBC принимают абсолютно одинаковый вид (st). 

В равносильны тогда и только тогда когда формула A~B

является тавтологией.
2)Формула В логически следует из А тогда и только тогда, когда АВ – тавтология.
Следствие:
AB  AB – противоречие.

Доказательство.
2) Необходимость:
Пусть I(A)= И. Тогда из определения следования вытекает I(B)=И  I(AB)=И. Таким образом формула AB тавтология.
Достаточность: Пусть AB – тавтология. Тогда для всякой I, такой что I(A)=И необходимо I(B)=И, иначе I(AB)=Л. Что означает, что A является логическим следствием B.

эквиваленцию можно с использованием правила замены и равносильностей (AB)~(

AB) и A~B(AB)(BA).
Пронести отрицания можно с помощью снятия двойного отрицания и законов де Моргана

Определение. Литера есть атом или отрицание атома.
Определение. Формула А находится в конъюнктивной нормальной форме тогда и только тогда, когда она имеет вид
A= A1  A2  …  AN,
где каждая Ai есть дизъюнкция литер.
Определение. Формула А находится в дизъюнктивной нормальной форме тогда и только тогда, когда она имеет вид
A= A1 A2 … AN,
где каждая Ai есть конъюнкция литер.