Шпаргалка по "Математическая логика"

2.Применить критерий тождественной истинности к формуле А. Если А - тождественно истин- 
ная. то А - тождественно ложная. В противном случае А - выполнимая формула.

 

Критерии тождественной истинности формулы алгебры логики, используя ее КНФ.

Для того, чтобы  формула алгебры логики А была тождественно истинна, необходимо и достаточно, чтобы любая элементарная дизъюнкция, входящая в КНФ А, содержала переменную и ее отрицание.

Критерий тождественной ложности формулы алгебры логики, используя  ее ДНФ.

Для того, чтобы формула  алгебры логики А была тождественно ложной, необходимо и достаточно, чтобы любая конъюнкция, входящая в ДНФ А, содержала переменную и ее отрицание.

8. Понятие булевой функции. Способы задания  булевых функций.

Определение: Переменная x называется булевой, если она способна принимать только два значения 0 и 1.

Определение: Функция f(x₁,x₂,…,x_n) называется булевой (или логической, или функцией алгебры логики, или переключательной), если все ее аргументы x[i] являются булевыми, а сама функция также может принимать только два значения 0 и 1. Множество всех булевых функций от переменных x₁,x₂,…,x_n обозначают через P₂.

Способы задания булевых  функций. К таковым способам задания стандартно относятся: 
1) табличный; 
2) графический; 
3) аналитический.

Приведем таблицы истинности, обозначения и названия булевых функций одного и двух аргументов. В таблице представлены все (их 2^2^1=4) функции одного аргумента.

x	0 1	Обозначение	Название
0	0 0	0	Нуль, const 0
1	0 1	x	Повторение x
2	1 0	¬x, x	Отрицание x, не x
3	1 1	1	Единица, const 1

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

9. Нормальные  формы булевых функций.

Соглашение. Конъюнкцию переменных двух переменных x и y будем обозначатьчерез xy .

Определение. Конъюнктивным одночленом от переменных x1, x2, ..., xn называется конъюнкция этих переменных или их отрицаний.

Примеры:

(1) x1 ;

(2) x1x2 ;

(3) x1x2’x3 ;

(4) x2x1’x3x2’x1 .

Определение. Дизъюнктивным одночленом от переменных x1, x2, ..., xnназывается дизъюнкция этих переменных или их отрицаний.

Примеры:

(1) x1 ;

(2) x1 ∨ x3 ;

(3) x1’∨ x2 ∨ x3 ;

(4) x1 ∨ x2 ∨ x1 ∨ x3’∨ x4 ∨ x2’.

Определение. Дизъюнктивной нормальной формой (ДНФ) называетсядизъюнкция конъюнктивных одночленов, т.е. выражение вида K1 ∨ K2 ∨ ... ∨ Kp ,где все Kj (j = 1,2, ..., p) являются конъюнктивными одночленами.

 

Определение. Конъюнктивной нормальной формой (КНФ) называется конъюнкция дизъюнктивных одночленов, т.е. выражение вида D1D2...Dq , где все

Dj (j = 1,2, ..., q) являются дизъюнктивными одночленами.

Примеры:

x1 ∨ x1x2 ∨ x2x3’∨ x1x3’∨ x1x1’x2x3x3’— дизъюнктивная нормальная форма от переменных x1, x2, x3 ;

(x1)(x2 ∨ x3’)(x3 ∨ x3’∨ x4)(x3 ∨ x4)(x1 ∨ x4’) — конъюнктивная нормальная форма от переменных x1, x2, x3, x4 .

 

Теорема: Всякая булева функция f(x1, x2, ..., xn) может быть представлена в виде суперпозиции конъюнкции, дизъюнкции и отрицания; причем знак отрицания стоит только непосредственно около переменной и не стоит ни перед одной из внутренних скобок.

Следствие. Для всякой булевой функции от переменных x1, x2, ..., xn имеется равная ей дизъюнктивная (конъюнктивная) нормальная форма.

 

Определение. Конъюнктивный (дизъюнктивный) одночлен от переменных

x1, x2, ..., xn называется  совершенным, если в него от  каждой пары { xj, xj’} (j =1,2, ..., n) входит только один представитель ( xj или xj’).Определение. Нормальная форма (дизъюнктивная или конъюнктивная) от

переменных x1, x2, ..., xn называется совершенной, если в нее входят только совершенные  одночлены (конъюнктивные или дизъюнктивные) от этих переменных.

10. Принцип двойственности для булевых функций. Самодвойственные функции.

Функция f*(x₁,…,x_n) называется двойственной к функции f(x₁,…,x_n), если

Принцип двойственности: Пусть функция F заданна суперпозицией функций f₀,…,f_n, где nÎN. Функцию F*, двойственную F, можно получить, заменив в формуле F функции f₀,…,f_n на двойственные им f₀^*,…,f_n^*.

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

f = f*

11. Системы булевых  функций. Специальные классы булевых  функций. Теорема Поста.

Системы булевых функций

Определение 11.1. Система булевых функций называется полной, если всякая булева функция является суперпозицией функций из этой системы.

Следующие системы булевых функций  являются полными: 1) {&,v,}: 2) {&, v,-}; 3) {&,-}; 4){v,-}.

БФ называется монотонной, если a<=b => f(a)<=f(b) для всех a,b принадлежащих bin(n). Сравниваются двоичные наборы не как двоичные числа а по всем битам.

Функция f(x₁; x₂;…x_n) называется монотонной, если для каждого s_1i£s_2i булевых векторов (s₁₁; s₁₂;……;s_1n) и (s₂₁;s₂₂;……;s_2n) выполняется условие: f(s₁₁;s₁₂;…;s_1i;…;s_1n)£f(s₂₁;s₂₂;…;s_2i;…;s_2n).

Полиномы Жегалкина, не содержащие конъюнкции двоичных переменных, т.е. P(x₁; x₂;…;x_n)=b₀×1Åb₁×x₁Å…Åb_n×x_n называют линейными.

Специальные классы булевых функций

• Говорят, что булева функция   сохраняет 0, если  . Обозначим   — класс всех булевых функций, сохраняющих 0.
• Говорят, что булева функция   сохраняет 1, если  . Обозначим   — класс всех булевых функций, сохраняющих 1.
• Булева функция   называется двойственной функцией для булевой функции  , если   для любых  .
• Булева функция   называется самодвойственной, если  . Класс всех самодвойственных булевых функций обозначим  .
• Введем на множестве   отношение порядка, полагая, что  . Булева функция   называется монотонной, если для любых  из неравенств  немедленно следует, что  . Класс всех монотонных функций обозначим  .
• Наконец, булева функция   называется линейной, если ее можно представить в виде следующего выражения (называемого полиномом Жегалкина степени не выше первой):   ,где   — постоянные, равные либо 0, либо 1. Символом   обозначим класс всех линейных булевых функций.

Теорема 11.3. Классы   являются собственными замкнутыми классами булевых функций.

Теорема Поста:

Теорема 11.4 (о полноте системы  булевых функций). Система булевых функций   является полной тогда и только тогда, когда в этой системе имеется функция, не принадлежащая классу  , имеется функция, не принадлежащая классу  , имеется функция, не принадлежащая классу  , имеется функция, не принадлежащая классу  , имеется функция, не принадлежащая классу  .

12. Формальные  аксиоматические теории. Основные этапы  построения.

Определение 28.1. Формальная аксиоматическая теория Г считается определенной, если выполнены следующие условия:

1. задан алфавит теории , представляющий собой некоторое счетное множество символов. Конечные последовательности символов алфавита теории называются словами или выражениями теории ;

 

2. имеется подмножество выражений  теории , называемых формулами теории  (обычно имеется эффективная процедура, позволяющая по данному выражению  определить, является ли оно формулой);

 

3. выделено некоторое множество  формул, называемых аксиомами теории  (обычно имеется эффективная процедура, позволяющая по данной формуле определить, является ли она аксиомой);

 

4. имеется конечное множество  отношений между формулами, называемых правилами вывода. При этом для  каждого существует целое положительное , такое, что для каждого множества, состоящего из  формул, и для каждой формулы  эффективно решается вопрос о том, находятся ли данные  формул в отношении  с формулой , и  если да, то  называется непосредственным следствием данных  формул по правилу .

 

Построенное ранее формализованное исчисление высказываний может служить примером формальной аксиоматической теории. Алфавит состоит из символов:  . Определено понятие формулы (см. определение 2.1). Из множества всех формул выделено множество всех аксиом (они определяются схемами аксиом  ).

Наконец, единственным отношением  , называемым правилом вывода, является тернарное отношение, в которое входят такие тройки формул  , что средняя формула   имеет вид  . Таким образом, формула   называется непосредственным следствием формул   и  . Это правило вывода было названо правилом заключения, или modus ponens (МР).

13. Исчисление  высказываний как формальная аксиоматическая  теория. Алфавит, формулы и подформулы исчисления высказываний.

Исчисление высказываний – это аксиоматическая логическая система интерпретацией которой является алгебра высказываний.

Алфавит исчисления высказываний состоит из символов трех категорий:

1. Символы первой категории: Эти символы будем называть переменными высказываниями.
2. Символы второй категории: они носят общее название логических связок. Первый из них – знак дизъюнкции или логического сложения, второй – знак конъюнкции или логического умножения, третий – знак  импликации  или логического следования и четвертый – знак отрицания.
3. Третью категорию составляет  пара символов (  ), называемая скобками.

Других символов исчисление высказываний не имеет.

 

Формулы исчисления высказываний представляют  собой последовательности символов алфавита исчисления  высказываний. Для обозначения формул будем пользоваться большими буквами латинского алфавита. Эти буквы не являются символами исчисления. Они представляют собой только условные обозначения формул.

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

1. Всякая переменная является формулой.
2. Если А и В- формулы , то слова - тоже формулы.
3. Никакая другая строчка символов не является формулой.

 

Одновременно  с понятием формулы вводится понятие подформулы или части формулы.

1. Подформулой элементарной формулы  является  она сама.

2. Если формула имеет вид , то ее  подформулами являются: она сама, формула А и все подформулы формулы А.
3. Если формула имеет вид (А*В)(здесь и в дальнейшем под символом * будем понимать любой из трех символов ), то ее подформулами являются: она сама, формулы А и В и все подформулы формул А и В.

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

Система аксиом исчисления высказываний:

I группа.  

I₁  x→(y→x);  

I₂  (x→(y→z))→((x→y)→(x→z)).

II группа.  

II₁   ; 

II₂   ;  

II₃   .

III группа.  

III₁  ;  

III₂  ;  

III₃  .

IV группа.  

IV₁   ;  

IV₂   ;  

IV₃   .

 

15. Определение доказуемой (выводимой) формулы. Примеры  доказательств.

 

Определение выводимой (доказуемой ) формулы.

• Всякая аксиома является доказуемой формулой.
• Формула, полученная из доказуемой формулы путем применения подстановки вместо переменной х  произвольной формулы В, есть доказуемая формула.
• Формула В, полученная из доказуемых формул А и   путем применения ПЗ, есть доказуемая формула.

 

Никакая другая формула исчисления высказываний не считается доказуемой .

   Процесс получения доказуемых формул будем называть доказательством (выводом) формул. Это процесс последовательного перехода от одной доказуемой формулы к другой с помощью аксиом, правила подстановки и правила заключения на каждом шаге (в определенном смысле это аналог равносильным преобразованиям в алгебре логики), так что вывод даже простой формулы может оказаться, в силу его многошаговости, достаточно громоздким.

16. Построение  выводов из совокупности формул. Правила  выводимости. Теорема дедукции.

 

Определение формулы, выводимой из совокупности Н.

1. Всякая формула А_i ,является формулой, выводимой из Н.
2. Всякая доказуемая формула  выводима из Н.
3. Если формулы С и С→В выводимы из совокупности Н, то формула В также выводима из Н.

 

Если  некоторая  формула В выводима из совокупности Н, то это записывают так: Н├В.