Совершенная ДНФ

Опр. ДНФ называется совершенной отн-но дан.мн-ва переем-х, если каждая переем-я входит в каждую элементарную конъюнкцию (с отрицанием или без отрицания), причем ровно один раз.Элементарные конъюнкции, вход.в СДНФ д.б.различными.Н-р:

1) xyz xyz– СДНФ от x, y, z.

2) xy– СДНФ от x, y, но не является СДНФ от x, y, z.

Замечания 1. const.º0 – СДНФ;

2. ДНФ, найденная табличным способом, является СДНФ.

3. F= – СДНФ от переменной x, но не является СДНФ от x, y, z, которая может быть из нее получена: F= = = – СДНФ от x, y, z.

Теорема. Всякая ф-ла ал-ры выс-й имеет равносильную ей СДНФ, кот.опр-ся с точ-ю до порядка записи элемент-х конъюнкций.

2. Понятие булевой функции. Таблица истинности формулы Подставляя в ф-лу вместо пропозициональных пер-x, y, z,… значения 0,1, и выполняя действия, мы б.пол-ть знач-я ф-лы.Опр. Булевой ф-цией наз-ся ф-ция, зад. на мн-ве {0,1} и приним.знач-я из этого же мн-ва.Каждой ф-ле алгебры в-й соответствует булева ф-ция и притом единственная. Таблица знач-й этой ф-ции наз-ся таблицей истинности.Лемма. Сущ. 2ⁿ наборов, элементами кот-х явл-ся нули и единицы, длины n. (Длина набора – число символов, входящих в набор).Док-во методом математической индукции:

1. Пусть n=1: Имеем 2 набора {0},{1}.

2. Предположим, что утверждение леммы справедливо для n=k. Существует 2^k наборов длины k, элементами кот-х явл-ся нули и единицы.

Î{0,1}

Применим к набору (1) след. преобразование: сначала допишем в конце набора 0, а затем 1. В рез-те, из одного набора длины k получим два набора длины (k+1).

Таким же образом поступим с каждым из 2^k наборов. Всего наборов получится:2×2^k=2^k+1.По принципу мат.индукции утверждение леммы справ-во для люб.нат.числа n.Теорема. Существует 2²ⁿ булевых функций от n переменных.Р!булевы ф-ции от 2 пер-х:

x	y	f0	f1	f2	f3
f4	f5	f6	f7	f8	f9
f10	f11	f12	f13	f14	f15

f₀º0 – константа, f₁=x&y – конъюнкция

f₂= , f₃=x – повторение аргумента x, f₄= ,f₅=y – повторение аргумента y, f₆= , f₇=xÚy – дизъюнкция. f₈= – стрелка Пирса, f₉=x«y – эквивалентность, f₁₀= – инверсия y, f₁₁=y®x – импликация,f₁₂= – инверсия x, f₁₃=x®y – импликация,f₁₄= – штрих Шеффера,f₁₅º1 – константа. Среди перечисленных 16-ти ф-ций две ф-ции – константы, 4 ф-ции зависят от одной пер-й и 10 – от 2-х.Особую роль играют булевы ф-ции тождественно рав.1 при люб.наборах знач-й пер-х.

Опр. Формула (АВ) наз-ся тождественно истинной (тавтологией), если она принимает значение «истина» при люб.знач-х переем-х, входящих в ф-лу.

Пример: F(x,y)=(x®y) Ú (y®x)

1.ВЫСКАЗЫВАНИЯ.Алгебра высказываний.Высказывания и операции над ними Выс-е–основное,неопределяемое понятие.Любые утверждения,об ист-ти или лож-ти кот-х имеет смысл говорить, мы б.наз-ть высказываниями, при этом мы можем не знать, истинно ли данное выс-е или нет. Выс-ми, например, б.след. утверждения:- «Кама является одной из крупнейших рек России»;- «8 – есть простое число»;- «9000 –я цифра в десятичной записи числа π есть 7». Первое из этих утвержд-й истинно,второе–ложно; ист-ть или лож-ть третьего утверж-я нам неизвестна.Выс-я б.обоз-ть лат.буквами (прописными и строчными, с индексами и без них): A, B, C,..., A1, A2, C3, …,p, q, r, …, q2, q3 ….Итак, пусть p, q, r –выс-я или пропозициональные (высказывательные) переменные, кот.м.принимать два значения истинности: Л (0; F – false) и И (1; Т – true). Разл. образом сочетая выс.-я м\д собой, мы м.пол-ть новые выс-я. Н-р, из двух выс-й: «Пермь – столица Пермского края» и «8 – есть простое число» м.пол-ть след.выс-я:-«Пермь–столица Перм. края и 8 – есть пр. число»,- «Пермь – столица Пермского края или 8 – есть простое число»,- «Если Пермь – столица Пермского края, то 8 – есть простое число»,- «Пермь – столица Пермского края тогда и только тогда, когда 8 – есть простое число».Из перв.выс-я м. получить новое выс-е - «неверно, что Пермь является столицей Пермского края», т.е. выс-я, явл.отрицанием первого.Приведенные сочетания выс-й образуются при помощи слов «И»; «ИЛИ», «ЕСЛИ…, ТО», «ТОГДА И ТОЛЬКО ТОГДА, КОГДА…», «НЕ». В математической логике для обозначения этих основных типов сочетаний, имеющих название, используются спец.символы:p q(p&q, pq,p∙q)– читается «пэ и ку») – обозначает сложное выс-е, истинное только в том случае, когда p и q оба истинны. Такое выс-е называют конъюнкцией (от лат. conjunctio – союз, связь) высказываний p и q. p q(читается «пэ или ку») обозначает сложное выс-е, истинное тогда лишь, когда по крайней мере одно из выс-й истинно (м.быть истинными оба выс-я). Такое выс-е наз-т дизъюнкцией (от лат. disjunctio – различение, разобщение) высказываний p и q.p q(p q, p q)– читается «если пэ, то ку», «пэ достаточно для ку», «ку необходимо для пэ», «ку с необходимостью следует из пэ», «из пэ следует ку», «пэ влечет ку») обозначает сложное выс-е, кот.ложно только в том случае, когда p истинно, а q ложно и истинно во всех остальных случаях. Такое выс-е называют импликацией (от лат. implico – тесно связываю) выс-й p и q. В импликативном высказывании p q различают антецедент (основание) – высказывание p и консеквент (следствие)–выс-е q.p q(p q, p q, p q)– читается «пэ тогда и только тогда, когда ку», «пэ если и только если ку», «пэ в том и только том случае, когда ку») обоз-т сложное выс-е, истинное, когда выс-я p и q одновременно оба истинны или оба ложны. Такое выс-е наз-т эквивалентностью выс-p и q. – читается «не пэ», «неверно, что пэ») – есть противоположность p. Обозначает выс-е, истинное, если p ложно и ложное, если p истинно. Такое выс-е наз-т отрицанием высказывания p.Замечание 1. Символы &, , , соответствуют бинарным операциям: новое высказывание сопоставляют двум высказываниям p и q, а символ выражает определенную на том же мн-ве унарную операцию: сопоставляет новое высказывание одному высказыванию p.Замечание 2. Слова «и»; «или», «если…, то», «тогда и только тогда, когда…», являющиеся связками в нашем обычном языке, в мат.логике получают несколько иной смысл.В обычном языке союз «и» исп-ся, как правило, для объединения двух предложений, соответствующих друг другу по смыслу в некот.связном повествовании как это бывает при описании последовательности событий (Елена хорошо подготовилась к экзамену Однако в логике «И» м.соединять люб.предл-я, совершенно незав-мо от наличия смыслового соответствия м\д ними.Аналог.союз ИЛИ в обычном языке употребляется в двух смыслах – в смысле исключающем от лат. aut («p или q, но не оба») и в смысле неисключающем от лат. vel («p или q, или оба). Именно в последнем смысле мы б.исп-ть союз ИЛИ чаще. И здесь опять несущественна смысл.зав-ть соединяемых выс-й.Не сущ-на смысловая связь в логике между выс-ми и при построении импликации, хотя в обычном языке сложное предл-е «если p, то q» предп-т м\д p и q отн-е посылки и следствия, или же причины и обусловленного ею дей-я.(Если б. дождь, то мы не пойдем на прогулку).В логике для ис-ти импликации дост-но, чтобы p было ложно или q – истинно.Т.о.,выс-я типа:– Если 7 – простое число, то 2´2=4;– Если 8 – простое число, то 2´2=4;-Если 8 – простое число, то 2´2=5 д.считаться истинным. Утверждение «p тогда и только тогда, когда q» не означает в логике, что составляющие предл-я p и q имеют одно и то же знач-е или один и тот же смысл, оно означает лишь выск-е, кот.истинно, когда оба выс-я истинны или ложны.Все, что говорилось о лог.смысле конъюнкции, дизъюнкции,импликации, эквивалентности и отрицания м.просто и наглядно проиллюстрировать с пом-ю Т.Н.таб-ц истинности.В таблицах выпис-ся всевозможные комбинации ист-х и лож-х зн-й составл.выс-й, а в результирующей колонке указ-ся ист-ть или лож-ть сложного выс-я для кажд.такой комбинации. Б.сопоставлять ист-му выс-ю символ 1, а ложному – символ 0.Вот как выглядят т-цы истинности для &, , , и :

p	q	P&q	p q	P q	p q

Понятие формулы алгебры выс-й. Опр. Алфавитом наз-ся произв.мн-во символов. Введем алфавит, сост.из след. групп символов:x, y, z, p, …А, В,… – пропозициональные переем-е;&, , , и :– лог.связки;(,) – 2 технических символа.Опр. (ф-лы алгебры выск-й):Каждая отдельно взятая пропозицион-я перем-я есть ф-ла алгебры выс-й. Ф-лы такого вида наз-ся простейшими (атомами).Если x – формула ал-ры выс-й (АВ), то (Øx) – ф-ла (АВ).Если x и y – ф-лы ал-ры выс-й, то (x&y), (xÚy), (x®y), (x«y) – тоже ф-лы (АВ).Никаких др.ф-л (АВ), кроме получающихся сог-сно п.п.1–3 нет.Опр-я такого типа наз-ся индуктивными. В них имеются прямые пункты (1,2,3), где задаются объекты, к.в дальнейшем именуются определяемым термином и косвенный пункт (4), в к.говорится,что такие объекты исчерпываются зад.в прямых пунктах. Среди прямых пунктов им-тся базисные (1), где указ-ся нек.конкретные объекты, именуемые в дал.определяемым термином, и индуктивные пункты (2,3), где даются правила получения определяемых объектов из уже имеющихся объектов, в частности из объектов, перечисл-х в базисных пунктах.Зам-е: «О силе связок».Для упрощения записи формул (уменьшения числа скобок в них) будем считать, что:порядок выполнения лог.операций над выс-ми д.б.след.:Ø, &, Ú, ®, «внешние скобки, заключающие внутри себя все остальные символы, составл.ф-лу, м.опускать.Учитывая это соглашение, а также опустив знак конъюнкции, ф-лу м.зап-ть в виде .При чтении ф-ла м.б.названа по «последней» операции. Запис.ф-ла П.С. импл-цию.