печать2. печать (2). 2. Высказывания и логические операции над ними. Таблицы истинности. 3
 Скачать 43.79 Kb.
|
B, А <=> В, А = В | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| I. Основные равносильности | ||
| 1 | x ˄ x ≡ x | Законы идемпотентности |
| 2 | x ˅x ≡ x | |
| 3 | x ˄ 1≡ x | Законы нуля и еденицы |
| 4 | x ˅ 1 ≡ 1 | |
| 5 | x ˄ 0 ≡ 0 | |
| 6 | x ˅ 0 ≡ x | |
| 7 | x ˄ x ≡ 0 | Закон протеворечия |
| 8 | x ˅ x ≡ 1 | Закон исключённого третьего |
| 9 | x ≡ x | Закон двойного отрицания |
| 10 | x ˄ ( y ˅ x ) ≡ x | Законы поглощения |
| 11 | x ˅ ( y ˄ x ) ≡ x | |
| 12 | ( x ˄ y ) ˅ ( x ˄ y) ≡ x | Формулы расщепления |
| 13 | (x ˅ y ) ˄ ( x ˅ y) ≡ x | |
| II. Равносильности, выражающие одни логические операции через другие | ||
| 1 | x ↔ y ≡ (x → y) ˄ (y → x) | Основная формула доказательств теорем существования |
| 2 | x → y ≡ x ˅ y | |
| 3 | x ˄ y ≡ x ˅ y | Законы де Моргана |
| 4 | x ˅ y ≡ x ˄ y | |
| 5 | x ˄ y ≡ x ˅ y | |
| 6 | x ˅ y≡ x ˄ y | |
| III. Равносильности, выражающие основные законы алгебры высказываний | ||
| 1 | x ˄ y ≡ y ˄ x | Коммутативные законы |
| 2 | x ˅ y ≡ y ˅ x | |
| 3 | x ˄ (y ˄ z)≡ (x ˄ y) ˄ z | Ассоциативные законы |
| 4 | x ˅ (y ˅ z) ≡ (x ˅ y) ˅ z | |
| 5 | x ˄ (y ˅ z) ≡ (x ˄ y) ˅ (x ˄ z) | Дистрибутивные законы |
| 6 | x ˅ (y ˄ z) ≡ (x ˅ y) ˄ (x ˅ z) | |
| 7 | x → y ≡ y → x | Закон контрапозиции |
| | | |
Закон двойственности:
Определение : Формулы A и A* называются двойственными формулами, если А* получается из А путем замены в ней каждой операции на двойственную.
Дизъюнктивная нормальная форма и совершенная 'дизъюнктивная нормальная форма (ДНФ и СДНФ).
Элементарной конъюнкцией называется конъюнкция нескольких переменных, взятых с отрицанием или без отрицания, причём среди переменных могут быть одинаковые.
Всякую дизъюнкцию элементарных конъюнкций
Назовём дизъюнктивной нормальной формой, то есть ДНФ.
Совершенная дизъюнктивная нормальная форма формулы (СДНФ) это равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций, обладающая свойствами
1. Каждое логическое слагаемое формулы содержит все переменные, входящие в функцию F(x1,x2,...xn)
2. Все логические слагаемые формулы различны
3. Ни одно логическое слагаемое не содержит переменную и её отрицание
4. Ни одно логическое слагаемое формулы не содержит одну и ту же переменную дважды.
Конъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма (КНФ и СКНФ).
Элементарной дизъюнкцией называется дизъюнкция нескольких переменных, взятых с отрицанием или без отрицания, причём среди переменных могут быть одинаковые.
Всякую конъюнкцию элементарных дизъюнкций
Назовём конъюнктивной нормальной формой, то есть КНФ.
Совершенная конъюнктивная нормальная форма формулы (СКНФ) это равносильная ей формула, представляющая собой конъюнкцию элементарных дизъюнкций, удовлетворяющая свойствам:
1. Все элементарные дизъюнкции содержат все переменные, входящие в функцию F(x1,x2,...xn)
2. Все элементарные дизъюнкции различны
3. Каждая элементарная дизъюнкция содержит переменную один раз
4. Ни одна элементарная дизъюнкция не содержит переменную и её отрицание
Критерии тождественной истинности и ложности формулы.
Все формулы алгебры логики делятся на три класса:
тождественно истинные,
тождественно ложные и
выполнимые.
Формулу А называют выполнимой, если она принимает значение «истина» хотя бы на одном наборе значений входящих в нее переменных и не является тождественно истинной.
Алгоритм определения класса формулы А
1.Применить критерий тождественной истинности к формуле А. Если А - тождественно истинная,
то задача решена. В противном случае перейти к шагу 2.
2.Применить критерий тождественной истинности к формуле А. Если А - тождественно истин-
ная. то А - тождественно ложная. В противном случае А - выполнимая формула.
Критерии тождественной истинности формулы алгебры логики, используя ее КНФ.
Для того, чтобы формула алгебры логики А была тождественно истинна, необходимо и достаточно, чтобы любая элементарная дизъюнкция, входящая в КНФ А, содержала переменную и ее отрицание.
Критерий тождественной ложности формулы алгебры логики, используя ее ДНФ.
Для того, чтобы формула алгебры логики А была тождественно ложной, необходимо и достаточно, чтобы любая конъюнкция, входящая в ДНФ А, содержала переменную и ее отрицание.
Понятие булевой функции. Способы задания булевых функций.
Определение: Переменная x называется булевой, если она способна принимать только два значения 0 и 1.
Определение: Функция f(x1,x2,…,xn) называется булевой (или логической, или функцией алгебры логики, или переключательной), если все ее аргументы x[i] являются булевыми, а сама функция также может принимать только два значения 0 и 1. Множество всех булевых функций от переменных x1,x2,…,xn обозначают через P2.
Способы задания булевых функций. К таковым способам задания стандартно относятся:
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 рассматривают как функции, зависящие от пустого множества переменных.
Нормальные формы булевых функций.
Соглашение. Конъюнкцию переменных двух переменных 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 называется совершенной, если в нее входят только совершенные одночлены (конъюнктивные или дизъюнктивные) от этих переменных.
Принцип двойственности для булевых функций. Самодвойственные функции.
Функция f*(x1,…,xn) называется двойственной к функции f(x1,…,xn), если
Принцип двойственности: Пусть функция F заданна суперпозицией функций f0,…,fn, где nÎN. Функцию F*, двойственную F, можно получить, заменив в формуле F функции f0,…,fn на двойственные им f0*,…,fn*.
Функция, равная своей двойственной, называется самодвойственной.
f = f*
Системы булевых функций. Специальные классы булевых функций. Теорема Поста.
Системы булевых функций
Определение 11.1. Система булевых функций называется полной, если всякая булева функция является суперпозицией функций из этой системы.
Следующие системы булевых функций являются полными: 1) {&,v,}: 2) {&, v,-}; 3) {&,-}; 4){v,-}.
БФ называется монотонной, если a<=b => f(a)<=f(b) для всех a,b принадлежащих bin(n). Сравниваются двоичные наборы не как двоичные числа а по всем битам.
Функция f(x1; x2;…xn) называется монотонной, если для каждого s1i£s2i булевых векторов (s11; s12;……;s1n) и (s21;s22;……;s2n) выполняется условие: f(s11;s12;…;s1i;…;s1n)£f(s21;s22;…;s2i;…;s2n).
Полиномы Жегалкина, не содержащие конъюнкции двоичных переменных, т.е. P(x1; x2;…;xn)=b0×1Åb1×x1Å…Åbn×xn называют линейными.
Специальные классы булевых функций
Говорят, что булева функция сохраняет 0, если . Обозначим — класс всех булевых функций, сохраняющих 0.
Говорят, что булева функция сохраняет 1, если . Обозначим — класс всех булевых функций, сохраняющих 1.
Булева функция называется двойственной функцией для булевой функции , если для любых .
Булева функция называется самодвойственной, если . Класс всех самодвойственных булевых функций обозначим .
Введем на множестве отношение порядка, полагая, что . Булева функция называется монотонной, если для любых из неравенств немедленно следует, что . Класс всех монотонных функций обозначим .
Наконец, булева функция называется линейной, если ее можно представить в виде следующего выражения (называемого полиномом Жегалкина степени не выше первой): ,где — постоянные, равные либо 0, либо 1. Символом обозначим класс всех линейных булевых функций.
Теорема 11.3. Классы являются собственными замкнутыми классами булевых функций.
Теорема Поста:
Теорема 11.4 (о полноте системы булевых функций). Система булевых функций является полной тогда и только тогда, когда в этой системе имеется функция, не принадлежащая классу , имеется функция, не принадлежащая классу , имеется функция, не принадлежащая классу , имеется функция, не принадлежащая классу , имеется функция, не принадлежащая классу .
Формальные аксиоматические теории. Основные этапы построения.
Определение 28.1. Формальная аксиоматическая теория Г считается определенной, если выполнены следующие условия:
задан алфавит теории , представляющий собой некоторое счетное множество символов. Конечные последовательности символов алфавита теории называются словами или выражениями теории ;
имеется подмножество выражений теории , называемых формулами теории (обычно имеется эффективная процедура, позволяющая по данному выражению определить, является ли оно формулой);
выделено некоторое множество формул, называемых аксиомами теории (обычно имеется эффективная процедура, позволяющая по данной формуле определить, является ли она аксиомой);
имеется конечное множество отношений между формулами, называемых правилами вывода. При этом для каждого существует целое положительное , такое, что для каждого множества, состоящего из формул, и для каждой формулы эффективно решается вопрос о том, находятся ли данные формул в отношении с формулой , и если да, то называется непосредственным следствием данных формул по правилу .
Построенное ранее формализованное исчисление высказываний может служить примером формальной аксиоматической теории. Алфавит состоит из символов: . Определено понятие формулы (см. определение 2.1). Из множества всех формул выделено множество всех аксиом (они определяются схемами аксиом ).
Наконец, единственным отношением , называемым правилом вывода, является тернарное отношение, в которое входят такие тройки формул , что средняя формула имеет вид . Таким образом, формула называется непосредственным следствием формул и . Это правило вывода было названо правилом заключения, или modus ponens (МР).
Исчисление высказываний как формальная аксиоматическая теория. Алфавит, формулы и подформулы исчисления высказываний.
Исчисление высказываний – это аксиоматическая логическая система интерпретацией которой является алгебра высказываний.
Алфавит исчисления высказываний состоит из символов трех категорий:
Символы первой категории: Эти символы будем называть переменными высказываниями.
Символы второй категории: они носят общее название логических связок. Первый из них – знак дизъюнкции или логического сложения, второй – знак конъюнкции или логического умножения, третий – знак импликации или логического следования и четвертый – знак отрицания.
Третью категорию составляет пара символов ( ), называемая скобками.
Других символов исчисление высказываний не имеет.
Формулы исчисления высказываний представляют собой последовательности символов алфавита исчисления высказываний. Для обозначения формул будем пользоваться большими буквами латинского алфавита. Эти буквы не являются символами исчисления. Они представляют собой только условные обозначения формул.
Определение формулы исчисления высказываний.
Всякая переменная является формулой.
Если А и В- формулы , то слова - тоже формулы.
Никакая другая строчка символов не является формулой.
Одновременно с понятием формулы вводится понятие подформулы или части формулы.
1. Подформулой элементарной формулы является она сама.
Если формула имеет вид , то ее подформулами являются: она сама, формула А и все подформулы формулы А.
Если формула имеет вид (А*В)(здесь и в дальнейшем под символом * будем понимать любой из трех символов ), то ее подформулами являются: она сама, формулы А и В и все подформулы формул А и В.
Система аксиом исчисления высказываний. Основные и производные правила вывода.
Система аксиом исчисления высказываний:
I группа.
I1 x→(y→x);
I2 (x→(y→z))→((x→y)→(x→z)).
II группа.
II1 ;
II2 ;
II3 .
III группа.
III1 ;
III2 ;
III3 .
IV группа.
IV1 ;
IV2 ;
IV3 .
Определение доказуемой (выводимой) формулы. Примеры доказательств.
Определение выводимой (доказуемой ) формулы.
Всякая аксиома является доказуемой формулой.
Формула, полученная из доказуемой формулы путем применения подстановки вместо переменной х произвольной формулы В, есть доказуемая формула.
Формула В, полученная из доказуемых формул А и путем применения ПЗ, есть доказуемая формула.
Никакая другая формула исчисления высказываний не считается доказуемой .
Процесс получения доказуемых формул будем называть доказательством (выводом) формул. Это процесс последовательного перехода от одной доказуемой формулы к другой с помощью аксиом, правила подстановки и правила заключения на каждом шаге (в определенном смысле это аналог равносильным преобразованиям в алгебре логики), так что вывод даже простой формулы может оказаться, в силу его многошаговости, достаточно громоздким.
Построение выводов из совокупности формул. Правила выводимости. Теорема дедукции.
Определение формулы, выводимой из совокупности Н.
Всякая формула Аi ,является формулой, выводимой из Н.
Всякая доказуемая формула выводима из Н.
Если формулы С и С→В выводимы из совокупности Н, то формула В также выводима из Н.
Если некоторая формула В выводима из совокупности Н, то это записывают так: Н├В.
Нетрудно видеть, что класс формул, выводимых из совокупности Н, совпадает с классом доказуемых формул в случае, когда совокупность Н содержит только доказуемые формулы, и в случае, когда Н пуста.
Если же совокупность формул Н содержит хотя бы одну не доказуемую формулу, то класс формул, выводимых из Н, шире класса доказуемых формул.
Правила выводимости:
Основные правила выводимости:
1. H ├ A Это правило следует непосредственно из определения вывода
H,W├A из совокупности формул : “Если А выводима из Н, то она вы-
водима из ”.
2. H,C ├ A,H├C
H├A .
3. H,C ├ A, W├C
H,W├A .
4. H ├ C→A
H,C├A .
5. Теорема дедукции: H, C├ A .
H├C→A
5а. Обобщенная теорема дедукции: {C1, C1, …, Ck}├ A
├C1 →(C2→(C3→…(Ck→A)…))
6. Правило введения конъюнкции: H├A,H├B (показано в примере §4).
H├
7. Правило введения дизъюнкции: H,A├C;Н,B├C .
H, ├C
Теорема Дедукции:
Пусть Г – множество формул исчисления L; А и В – формулы, и пусть
Г, А L В. Тогда Г L (А В). В частности, при пустом Г, из выводимости А L В вытекает теорема: L А В.
Связь алгебры высказываний с исчислением высказываний.
Формулы исчисления высказываний можно интерпретировать как формулы алгебры высказываний. Для этого будем трактовать переменные исчисления высказываний как переменные алгебры высказываний, т. е. переменные в содержательном смысле, принимающие два значения: истина и ложь (1 и 0).
Операции определим так же, как в алгебре высказываний.
При этом всякая формула исчисления высказываний при любых входящих в нее переменных будет принимать одно из значений 1 или 0, вычисляемое по правилам алгебры высказываний.
Введем понятие значения формулы исчисления высказываний. Пусть А- формула исчисления высказываний, х1,х2,…,хn- попарно различные переменные, среди которых находятся все переменные, входящие в формулу А. Обозначим через а1, а2,…,аn набор значений этих переменных, состоящих из 1 и 0, длины n. Очевидно, что вектор (а1, а2,…,аn) имеет 2n значений.
Имеют место три теоремы, которые устанавливают связь между основными фактами алгебры высказываний и исчисления высказываний.
Теорема 1.
Каждая формула, доказуемая в исчислении высказываний, является тождественно истинной в алгебре высказываний.
Формулировка этой теоремы содержит в себе три положения:
1)Каждая аксиома исчисления высказываний – тождественно истинная формула в алгебре высказываний.
2)Правило подстановки, примененное к тождественно истинным формулам, приводит к тождественно истинным формулам.
3)Правило заключения, примененное к тождественно истинным формулам, приводит к тождественно истинным формулам.
Теорема 2.( о выводимости).
Пусть А –некоторая формула исчисления высказываний; х1,х2,…,хn – набор переменных, содержащих все переменные, входящие в формулу А; а1, а2,…,аn – произвольный фиксированный набор значений этих переменных. Обозначим через Н конечную совокупность формул
, где
Тогда:
Если Ra1,a2,..,an(A)=1, то H├A .
Если Ra1,a2,..,an(A)=0, то H├ , где Ra1,a2,..,an(A)–значение формулы А на наборе а1, а2,…,аn.
Теорема 3.
Каждая тождественно истинная формула алгебры высказываний доказуема в исчислении высказываний.
Разрешимость и непротиворечивость исчисления высказываний.
1.Проблема разрешимости исчисления высказываний.
Проблема разрешимости исчисления высказываний заключается в доказательстве существования алгоритма, который позволил бы для любой заданной формулы исчисления высказываний определить, является ли она доказуемой или не является.
Имеет место теорема: проблема разрешимости для исчисления высказываний разрешима.
Действительно, любая формула исчисления высказываний может рассматриваться как формула алгебры высказываний, и, следовательно, можно рассматривать ее логические значения на различных наборах значений входящих в нее переменных.
Пусть А – любая формула исчисления высказываний, а х1,х2,…,хn – перечень входящих в нее переменных. Вычислим Ra1,a2,..,an(A) на всех наборах значений а1, а2,…,аn входящих в нее переменных. Если при этом Ra1,a2,..,an(A)=1, на всех наборах а1, а2,…,аn, то формула А – тождественно истинна, и, значит, по теореме о доказуемости тождественно истинной формулы она доказуема.
Если же существует набор значений переменных такой, что , то формула А – не тождественно истинная, и, значит, по теореме 1 §8 она не доказуема.
2. Проблема непротиворечивости исчисления высказываний.
Логическое исчисление называется непротиворечивым, если в нем не доказуемы никакие две формулы, из которых одна является отрицанием другой.
Иначе говоря, аксиоматическое исчисление называется непротиворечивым, если в нем не существует такая формула А, что доказуема как формула А, так и формула .
Проблема непротиворечивости заключается в выяснении вопроса: является данное исчисление непротиворечивым или нет?
Если в исчислении обнаруживаются доказуемые формулы вида А и , то такое исчисление называется противоречивым. В рассмотренном нами исчислении высказываний невозможно вывести одновременно формулы А и , т.е. это исчисление высказываний непротиворечиво.
Полнота исчисления высказываний. Независимость системы аксиом исчисления высказываний.
3.Проблема полноты исчисление высказываний.
Определение 1.
Аксиоматическое исчисление высказываний называется полным в узком смысле, если добавление к списку его аксиом любой недоказуемой в исчислении формулы в качестве новой аксиомы приводит к противоречивому исчислению.
Определение 2.
Исчисление высказываний называется полным в широком смысле, если любая тождественно истинная формула в нем доказуема.
Из этих определений следует, что проблема полноты исчисления высказываний содержит два вопроса:
Можно ли расширить систему аксиом аксиоматического исчисления путем добавления к ней в качестве новой аксиомы какой-нибудь недоказуемой в этом исчислении формулы?
Является ли всякая тождественно истинная формула алгебры высказываний доказуемой в исчислении высказываний?
Рассмотренное нами исчисление высказываний полно как в узком смысле, так и в широком.
4.Проблема независимости аксиом исчисления высказываний.
Для всякого аксиоматического исчисления возникает вопрос о независимости его аксиом. Вопрос этот ставится так : можно ли какую-нибудь аксиому вывести из остальных аксиом, применяя правила вывода данной системы?
Если для некоторой аксиомы системы это возможно, то эту аксиому можно исключить из списка аксиом системы, и логическое исчисление при этом не изменится, т. е. класс доказуемых формул останется без изменений.
Определение 3.
Аксиома А называется независимой от всех остальных аксиом исчисления, если она не может быть выведена из остальных аксиом. Система аксиом исчисления называется независимой, если каждая аксиома системы независима.
Рассмотренная нами система аксиом исчисления высказываний независима.