Тождества логики высказываний, правильные рассуждения.

Тождества логики высказываний, правильные рассуждения.

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

Формула называется выполнимой, если на некоторой оценке своего списка переменных она принимает значение 1. В последнем столбце таблицы истинности этой формулы есть хоть одна 1.

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

Формула называется опровержимой, если на некоторой оценке своего списка переменных она принимает значение 0. В последнем столбце таблицы истинности этой формулы есть хоть один 0.

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

 

Двойственность. Закон двойственности.

Логические символы и называют двойственными друг другу. Формула А двойственна формуле А, если она получена из А одновременной заменой и на двойственные. Например, формула F=A (B& C) двойственна формуле F =A& (B C). Это первый способ получения двойственной формулы. Теорема (принцип двойственности): если A B, то A B . Доказательство: Пусть на некоторой оценке s общего списка переменных для всех четырёх рассматриваемых формул формула A принимает значение 1. Тогда формула A, двойственная A , принимает значение 0 на оценке t, двойственной оценке s. Так как A B, то формула B тоже принимает значение 0 на оценке t. Отсюда формула B , двойственная B, принимает значение 1 на оценке s, двойственной оценке t. Поскольку оценка s произвольна, то получаем, что A B .

 

Разрешимость для логики высказываний. Контактные схемы.

Разрешимость для логики высказываний – это существует ли процедура, позволяющая для каждой формулы за конечное число шагов определить, является ли эта формула тавтологией. Логика высказываний разрешима, так как для каждой формулы можно построить её таблицу истинности.

Существует и другая процедура проверки того, что формула является тавтологией: формула является тавтологией тогда и только тогда, когда для каждой её КНФ в любую из элементарных дизъюнкций (скобок) входят одновременно какая-то переменная и её отрицание.

 

Нормальные формы формул. Теорема о единственности СДНФ и СКНФ.

Формула находится в дизъюнктивной нормальной форме (ДНФ), если она является дизъюнкцией (может быть и одночленной) элементарных конъюнкций. Например, формулы (x y) ( x y z), y (t & s), t, y находятся в ДНФ. Формула находится в конъюнктивной нормальной форме (КНФ), если она является конъюнкцией (может быть и одночленной) элементарных дизъюнкций. Например, формулы (x y) & ( x y z), y & (t s), t, y находятся в КНФ.

Из всех нормальных форм формулы выделим совершенные формы. Из ДНФ выделим Совершенную ДНФ (СДНФ). Формула находится в СДНФ относительно своего списка переменных, если каждый её дизъюнктивный член содержит по одному разу в прямом или инверсном виде все переменные формулы, и все её дизъюнктивные члены попарно различны. Например, формула в СДНФ: (x & y & z) (x & y & z) ( x & y & z).

Теорема Поста, её необходимость. Таблица Поста.

Теорема Поста: для того, чтобы система булевых функций F = {F1, …, Fm} была полной, необходимо и достаточно, чтобы для каждого из классов T , T , S, L и M нашлась функция Fj из системы F, не принадлежащая этому классу.

Доказательство необходимости: Классы T , T , S, L и M попарно различны и не совпадают с классом всех булевых функций. Если бы все функции системы F принадлежали какому-либо из этих классов, то в силу замкнутости этого класса система F не была бы полной. Необходимость теоремы доказана.

Функция	T	T	S	L	M
	+	+	-	-	+
	+	+	-	-	+
	-	-	+	+	-

 

f0

f1

f2

f3

f4

f5

f6

f7

f8

f9

f10

f11

f12

f13

f14

f15

T

+

+

+

+

+

+

+

+

-

-

-

-

-

-

-

-

T

-

+

-

+

-

+

-

+

-

+

-

+

-

+

-

+

S

-

-

-

+

-

+

-

-

-

-

+

-

+

-

-

-

L

+

-

-

+

-

+

+

-

-

+

+

-

+

-

-

+

M

+

+

-

+

-

+

-

+

-

-

-

-

-

-

-

+

 

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

Исчисление высказываний – это пример аксиоматической теории. ИВ определяется следующим образом:

1. Алфавит ИВ – это высказывательные переменные, скобки: (,) и логические символы и . Любой набор символов алфавита ИВ (даже бессмысленный) – это выражение ИВ.

2. Имеется подмножество выражений, называемое формулами ИВ. Формулы ИВ: а) все высказывательные переменные – это формулы; б) если A и B формулы, то A и A B тоже формулы. Формулы ИВ – это подмножество формул логики высказываний, содержащих только логические символы и .

3. Выделено некоторое подмножество формул, называемое аксиомами ИВ. Каковы бы не были формулы A, B и C, следующие формулы являются аксиомами ИВ:

A1. A (B A);

A2. (A (B C)) ((A B) (A C));

A3. ( B A) (( B A) B).

Выражения A1 – A3 называются схемами аксиом, поскольку каждое из них порождает бесконечное множество аксиом ИВ. Например, формула X (Y X) есть аксиома, полученная по схеме A1, а формула ( A A) (( A A) A) – аксиома ИВ, полученная по схеме A3.

4. Имеется правило вывода ИВ, позволяющее из предыдущих формул вывода получать последующие. Выводом в ИВ называется всякая последовательность формул ИВ (шагов вывода) такая, что любая формула есть либо аксиома или теорема ИВ, либо получена из предыдущих формул вывода с помощью правила вывода ИВ.

Формула T называется теоремой ИВ, если существует вывод, в которой эта формула является последней. Этот вывод называется выводом теоремы T ИВ: T. Слева от символа аксиомы ИВ, теоремы ИВ и то, что получено из них по правилу вывода ИВ, не записывается.

Правило вывода m.p.(modus ponens): если в выводе есть две формулы вида А В и А, то после них в выводе можно писать формулу В. Считается, что формула В получена по правилу m.p. из формул А и А В. Правило записывается так: или А, А В В. Порядок формул А и А В в выводе не важен (A может встретиться в выводе раньше А В, а может и позже), но формулу B нельзя писать раньше, чем А и А В появятся в выводе.

Все аксиомы ИВ – это тавтологии, что можно проверить по их таблице истинности. По правилу m.p. из тавтологий можно получить только тавтологии.

Тождества логики высказываний, правильные рассуждения.

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

Формула называется выполнимой, если на некоторой оценке своего списка переменных она принимает значение 1. В последнем столбце таблицы истинности этой формулы есть хоть одна 1.

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

Формула называется опровержимой, если на некоторой оценке своего списка переменных она принимает значение 0. В последнем столбце таблицы истинности этой формулы есть хоть один 0.

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