Мат. логика

6. Минимизация булевых функций методом Квайна.

1 этап: СДНФ → ДСНФ

2 этап: ДСНФ → МДНФ МДНФ – это ДНФ, которая среди эквивалентных ДНФ имеет минимальную длину.

fДНФ = – длина равна 5. 1 этап.

а) В основе первого этапа - операция неполного склеивания

, где А – произвольный конъюнктивный терм, не содержащий i-тую переменную.

– операция неполного склеивания б) Поглощение

А+АВ = А, где А,В – произвольные конъюнктивные термы, не содержащие общих переменных. Пример. 0-ой набор, 2,3,4,9,11,12,13,14 – на них f=1, на остальных f=0. Всего 4 переменных.

Ищем те, что склеиваются, т.е отличаются на 1 переменной ( и ).

1 и 2 склеивается, 1-4, 2-3, 3-6. 4-7, 5-6, 5-8, 7-8, 7-9. Пробуем склеить еще раз новые импликанты, не получается.

Так как мы выполнили операцию неполного склеивания, эта операция эквивалента → любая из неотмеченных – импликанта. То, что ни одну склеить нельзя, означает, что ни одну переменную выбросить нельзя → простая импликанта. Это ТСН алгоритм (полный перебор), ни одна не потеряна из пройденных импликант.

2 этап.

Строчки соответствуют простым импликантам, а столбцы – конституентам единицы. На пересечении i-той строки и j-того столбца ставится единица, если i-тая простая импликанта поглощает j-тую конституенту единицы.

Есть 4 правила, по которым можно уменьшать таблицу:

1.Обязательная простая импликанта

2.Доминирующая строка

3.Доминирующий столбец

4.Правило ветвления

1.Просматривает все столбцы, ищем столбец с одной единицей. Вычеркиваем столбы, которые накрыты.

2.Если существует 2 строки, и единицы одной строки полностью содержатся в другой, то эта строка доминирует, удаляем ту, где меньше единиц.

3. j – убираем, i – оставляем.

f мднф=

Потом строим схему (смотри ниже). Сложность схемы оценивается по количеству входов и выходов.

&

&

&

&

fМДНФ =

Для 6 переменных.

Для шести переменных действуем аналогично, как для 5, но теперь проверяем две оси симметрии.

Карта Карно Диаграмма Вейча

Пример.

Fмднф=

Неопределенности

Неопределенности - те значения функции, в которых значение не определенно. Обозначаются "-". Накрывать их не обязательно, на если они позволяют увеличить площадь квадрата, то использовать их обязательно.

fМДНФ =

8.Общезначимые формулы алгебры логики и их важнейшие свойства.

Общезначимые формулы играют особую роль в логике. Они на языке алгебры логики выражают законы логики. Общезначимые формулы истинны в силу своей структуры вне зависимости от истинных значений составляющих их формул.

Например, формула

тождественно равна 1 независимо от х.

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

Для утверждения «формула Е – общезначима» используется Е.

Так, , а F – необщезначимая формула F.

Остановимся на некоторых важнейших свойствах общезначимых формул.

Предложение 1

Если Е – общезначимая формула, содержащая переменные x1, x2, …xn, то формула Е*, получается из Е одновременной подстановкой формул А1, …Аn вместо переменных x1, x2, …xn соответственно, также общезначимая.

Предложение 2 Если ╞А и ╞А →В, то ╞В.

Предложение 3

╞А ~В  A≡B, читается как «формула ╞А ~В общезначима тогда и только тогда(), когда A≡B»

Предложение 4

╞Е  E ≡ 0 - противоречие

9.Отношение логического следования и его связь с общезначимостью.

Рассмотрим таблицы истинности следующих формул.

Пример: Из таблицы истинности видно, что при всех значениях х, у, при

Определение Из формулы А логически следует формула В, если всякий раз, когда А=1, В также принимает

значение 1. Следовательно B из A обозначается как А╞ В (из А логически следует В). При этом А – посылка, В – заключение.

Для нашего примера

Обратим внимание, что обратное неверно, то есть . Это видно из приведенных

таблиц истинности.

Обобщим это определение на случай n посылок.

Определение

Из функции А1, А2,…Аn следует В, если формула В=1, всякий раз, когда одновременно все посылки А1 = А2 =…= Аn = 1. Символически следование формулы B из формул А1, А2,…Аn обозначается как А1, А2,…Аn ╞ В. Использование для обозначения общезначимости и логического следования объясняется тем, что между этими понятиями устанавливается глубокая связь, которая объясняется предложением.

Предложение 5.

А1, А2,… Аn-1, Аn ╞ В  А1, А2,… Аn-1╞ Аn → В

В частности А ╞В  ╞А →В Доказательство:

1. Предположим, что А1, А2,…Аn ╞ В, А1, А2,… Аn-1 Аn → В

Тогда из последнего утверждения вытекает, что существует хотя бы один набор значений переменных x, y, z, … входящих хотя бы в одну из формул А1, А2,… Аn-1, B, при которых А1, А2,… Аn-1=1, а Аn → В = 0. По определению импликации это означает, что

Аn = 1, В = 0, тогда

А1=А2=…=Аn=1 В = 0 что противоречит условию А1, А2,…Аn ╞ В.

2.Предположим А1, А2,… Аn-1╞ Аn → В, а А1, А2,… Аn-1, Аn В

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

переменных x, y, z, … входящих хотя бы в одну из формул А1, А2,… Аn-1, B, при которых А1, А2,…

Аn-1=1, а B=0. Это означает что Аn → В = 0.

Но тогда А1, А2,… Аn-1 Аn → В, что противоречит условию А1, А2,… Аn-1Аn → В

Таким образом проверку следования А1, А2,… АnB можно свести и к проверке на общезначимость формулы

10. Анализ рассуждений средствами алгебры высказываний.

Пусть требуется проанализировать следующие рассуждения:

«Если десятичная запись данного целого числа оканчивается цифрой 2, то оно делится на 2. Десятичная запись данного целого числа не оканчивается цифрой 2, значит, оно не

делится на 2.»

Формализация рассуждений Обозначения:

х– десятичная запись данного целого числа оканчивается цифрой 2. у- данное целое число делится на 2.

Логическая структура рассуждения.



Общезначимость последней формулы установили от противного. Предположим, что найдутся также x, y, что

Тогда:

→→

Последняя система равенств непротиворечива. Это говорит о том, что наше предположение возможно, а исходное рассуждение неверно.

11. Анализ рассуждений с помощью диаграмм Вейча.

А1, А2,…,Аn ╞ В А1*А2*…*Аn ╞ В А1*А2*…*Аn → В

**

3 студента собрались после зачета, и выяснилось, что один из них не сдал. Двое других спросили его, в чем дело, и он рассказал им условия задачи, поставившей его в тупик.

1.если нельзя получить воду, то неверно, что есть водород и оксид магния

2.если есть углерод, но нет углекислого газа, то не было в наличии кислорода

3.если есть углекислый газ и вода, то можно получить углекислоту.

Вопрос: можно ли получить углекислоту?

MgO, O, H, C

х1 – нет воды х2 – есть водород и оксид магния

х3 – есть углерод х4 – есть углекислый газ х5 – есть кислород

х6 – есть углекислота

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

**

Если все посылки истинны и рассуждение правильно, то заключение правильно. В данном рассуждении заключение ложно, значит или рассуждение неправильно, или не все посылки истинны.

х – посылки истинны у – рассуждение правильно z – заключение верно

х*y → z, ╞ ( )

Ответ: рассуждение верно

**

Бог или бессилен предотвратить зло или он не желает предотвратить его (зло существует на земле). Чем Бог всемогущ, то неверно, что он бессилен предотвратить зло. Если Бог всеблаг, то неверно, что он не желает предотвратить зло. Следовательно, неверно, что Бог всемогущ и всеблаг.

х – Бог всемогуш у – Бог всеблаг

U – зло существует

V – Бог бессилен против зла