Если число π рационально, то π – алгебраическое число. Но оно не алгебраическое. Значит, π не рационально простое число простое число 641 x делится на 2 A B А – посылка, антецедент импликации В – заключение, консеквент И и Л, T(true) и F (False), 1 и 0

A B A если 2 2=5, то 2 2=4 если 2 2=5, то 3 3=1 Л И=Л Л=И если число x делится на 4, то оно делится на 2 если x делится на 2, то x делится на 4

Всякая пропозициональная переменная есть формула. Если A пропозициональная формула, то A пропозициональная формула. Если A и B пропозициональные формулы, то A B, A B и A B пропозициональные формулы n переменных p 1, p 2,..., p n.

((p q) p) (p (p q)) p=q=И (p q) ((p q) q) q B B B p 1, p 2,..., p n и (( ) ( )) (p q) ((p q) (q p))

(p q) (q p) ((p q) r) (p (q r)) (p q) (q p) ((p q) r) (p (q r)) (p (q r) ((p q) (p r)) (p q) ( p q) (p (p q)) p (pq) ( q p) p

(pq) (qp) - тавтология ((pq)p)p P Q и P Q для P и Q p q r p q и r p и q r 0 0 1? Теорема 2 (однозначность разбора). Пропозициональная формула, не являющаяся переменной, может быть представлена ровно в одном из четырех видов (A B), (A B), (AB) или A, где A и B – некоторые формулы, причем A и B (в первых трех случаях) восстанавливаются однозначно.

Польский логик Лукасевич предлагал обходиться без скобок, записывая в формулах сначала знак операции, а потом операнды (без пробелов и разделителей). Например, (a+b) (c+(d e)) в его обозначениях запишется как +ab+c de. Эту запись еще называют польской записью. Обратная польская запись отличается от нее тем, что знак операции идет после операндов.

(,,, ) полна в следующем смысле: Теорема 3 (Полнота системы связок). Любая булева функция n аргументов может быть записана в виде пропозициональной формулы. Теорема 4. Всякая булева функция может быть выражена формулой, находящейся в дизъюнктивной нормальной форме, а также формулой, находящейся в конъюнктивной нормальной форме.

(pq) ( p q),,, - неполна

00=0, 01=10=1 и 11=0 Теорема 5 (о полиномах Жегалкина). Всякая булева функция однозначно представляется таким полиномом. p q pq p p+1 p q p+q+pq

Теорема 6 (критерий Поста). Набор булевых функций является полным тогда и только тогда, когда он не содержится целиком ни в одном из пяти следующих "предполных классов": монотонные функции; функции, сохраняющие нуль; функции, сохраняющие единицу; линейные функции; самодвойственные функции.

A(BA) (A(BC))((AB)(AC)) (A B)A (A B)B A(B(A B)) A(A B) B(A B) (AC)((BC)(A BC)) A(AB) (AB)((A B) A) A

Единственным правилом вывода исчисления высказываний является правило со средневековым названием "modus ponens" (MP). Это правило разрешает получить (вывести) из формул A и (AB) формулу B. Modus ponens («правило вывода»): если A и AB выводимые формулы, то B также выводима.

(p(qp)), (p(qp))((pq)(pp)), ((pq)(pp))

При подстановке в теорему вместо пропозиционной переменой любой формулы получается теорема. В ФИВ выводимы следующие теоремы: A A, A A (закон двойного отрицания), A (A B) (из ложного, что угодно), ( B A) (A B), (A B) ( B A) (закон противоположности), A ( B (A B)).

(A(BC))((AB)(AC)) A(BC) - И, (AB)(AC) – Л (AB) - И, а AC – Л. A истинна, а C ложна A, (AB) и (A(BC)) истинны. B и (BC) истинны C истинна – противоречие

Лемма 1. Какова бы ни была формула D, формула (DD) является теоремой. 1. (D((DD)D))((D(DD))(D)) [аксио ма 2 при A=D, B=(DD), C=D]; 2. D((DD)D) [аксиома 1]; 3. (D(DD))(DD) [из 1 и 2 по правилу MP]; 4. D(DD) [аксиома 1]; 5. (DD) [из 3 и 4 по правилу MP].

Пусть Г – некоторое множество формул. ГА А => А Лемма 2 (о дедукции). Пусть Г – множество формул. Тогда ГАB тогда и только тогда, когда Г {A}B