49. Функциональная полнота. Теорема Поста.

50. Логические исчисления.

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

Опыт древних ученых был обобщен Аристотелем, который сформулировал конкретные виды рассуждений.

Аристотель рассмотрел 4 вида категорических рассуждения:

1. все А обладают свойством В.

2. некоторые А обладают свойством В.

3. все А не обладают свойством В.

4. некоторые А не обладают свойством В.

Были зафиксированы все случаи, когда из посылок такого вида выводятся предпосылки одного из этих видов.

(Пример: 1)все люди смертны, 2) Сократ – человек. Вывод – Сократ смертен)

Утверждения получили названия силлогизмы Аристотеля.

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

51. Высказывания. Формулы.

Высказывания

Элементы логических рассуждений – это утверждения, которые либо истинны, либо ложны.

Такие утверждения называются высказываниями.

Высказывания называются простыми, если они касаются 1 объекта. Обычно они обозначаются пропозициональными переменными, которые могут быть либо истинными, либо ложными.

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

Название	Обозначение
отрицание	, не
конъюнкция	точечка, и
дизъюнкция	Галочка вниз, или
имплекация	Стрілка вправо, если _, то _

Пример: если "холодно" и "идет дождь", то "одеться тепло" и "взять зонт".

Формула

Формула – это правильно построенное пропозициональное высказывание. Для исчисления высказываний справедлива след. таблица истинности.

А	В	¬ А	А и В	А или В	если А то В
F	F	T	F	F	T
F	T	T	F	T	T
T	F	F	F	T	F
T	T	F	T	T	T

52. Интерпретация формулы. Теорема.

Рассмотрим А(х₁, х₂… х_n) некоторую пропозициональную формулу, при этом х₁, х₂… х_n – пропозициональные переменные, образующие конкретный набор значений, приписанный переменным х₁, х₂… х_n называется интерпретацией формулы А.

Формула может быть истинной при одной интерпретации и ложной – при другой.

А(х₁, х₂… х_n) 

Формула, которая является истинной при некоторой интерпретации, называется выполнимой.

Формула, которая истинна при всех возможных интерпретациях, называется общезначимой ил тавтология.

Формула, которая является ложной при всех возможных интерпретациях, называется невыполнимой или противоречием.

А ¬А - тавтология

А и ¬ А - противоречие

А ¬ А – выполнение

А	¬А	А ¬А	А и ¬ А	А ¬ А
F	T	T	F	T
T	F	T	F	F

Теорема. Пусть А – некоторая формула, тогда:

1) если А – противоречие, то ¬А – тавтология и наоборот.

2) если А – тавтология, то ¬А – противоречие и наоборот.

3) если А – тавтология, то неверно, что А – противоречие, но не наоборот.

4) если А – противоречие, то неверно, что А – тавтология, но не наоборот.

Теорема. Если формулы А и А В тавтологии, то формула В – тавтология.

Док. докажем методом от противного.

I(B)=F, тогда I(A)=T, I(А B)=F – противоречие условию.

Посылка неверная, значит I(B)=T. Теорему доказано.