Минимизация методом карт Карно

Карты Карно – это графическое изображение таблиц истинности.

Пусть задана функция . Подмножество элементов , в которых , называется носителем функции f и обозначается через supp(f). Конечные пересечения подмножеств вида: называются кубиками. Кубики будут равны: , для некоторых и , таких, что . Если кубики являются максимальными, содержащимися в носителе, и попарно не пересекаются, то формула

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

x1	x2
	f(0,0)	f(0,1)
	f(1,0)	f(1,1)

	x2 x3
x1
	f(0,0,0)	f(0,0,1)	f(0,1,1)	f(0,1,0)
	f(1,0,0)	f(1,0,1)	f(1,1,1)	f(1,1,0)

	х3 x4
x1 x2
	f(0,0,0,0)	f(0,0,0,1)	f(0,0,1,1)	f(0,0,1,0)
	f(0,1,0,0)	f(0,1,0,1)	f(0,1,1,1)	f(0,1,1,0)
	f(1,1,0,0)	f(1,1,0,1)	f(1,1,1,1)	f(1,1,1,0)
	f(1,0,0,0)	f(1,0,0,1)	f(1,0,1,1)	f(1,0,1,0)

Кубикам будут соответствовать отрезки и квадраты. Рассмотрим примеры кубиков и соответствующих им логических произведений:

Возможно превращение кубиков в квадраты и отрезки после отождествления противоположных сторон карты Карно, например:

Логические произведения состоят из сомножителей, значения которых не изменяются внутри кубика. Если это значение равно 1, то для переменной берется сомножитель , а если это значение равно 0 – то сомножитель .

Пример

Для булевой функции:

найти дизъюнктивную нормальную форму с наименьшим числом логических слагаемых.

Решение. Составим карту Карно:

	х3 x4
x1 x2

Получаем 2 кубика: и . Внутри первого кубика не изменяются переменные и , и равны 0. Значит, первое слагаемое равно: . Внутри второго кубика не изменяются и , откуда второе слагаемое равно: . Следовательно, искомая дизъюнктивная нормальная форма равна: .

ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ

Математическая логика основана на понятии простого высказывания. Простое высказывание – это утверждение, про которое можно сказать, истинно оно или ложно при данных условиях. Из простых высказываний с помощью логических операций строятся составныевысказывания,которые далее будут называться просто высказываниями. Сохраняющее эти операции сопоставление каждому высказыванию одного из значений «истина» или «ложь», обозначаемых соответственно 1 или 0, называется интерпретацией исчисления высказываний.

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

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

Исчисление высказываний L

Алфавитом называется произвольное множество. Его элементы называются символами. Произвольная конечная последовательность символов называется словом. Слово может быть пустым.

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

Его алфавит состоит из символов , называемых логическими,и из символов, принадлежащих произвольному множеству Р, называемых нелогическими символами или буквами.

Синтаксис исчисления L определяется с помощью наименьшего подмножества S множества слов, такого, что

1) Р S;

2) Если A S и B S , то A S и (A B) S.

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

Аксиомами исчисления L называются формулы:

(A1) A (B A),

(A2) (A (B C)) ((A B) (A C)),

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

Здесь A, B, C – произвольные формулы. Поэтому в действительности мы имеем бесконечное множество аксиом, в каждой из групп A1, A2 и A3.

Правилом выводаModus Ponens называется множество троек формул (A,A B,B), которое позволяет паре формул (A,A B) поставить в соответствие формулу B, называющуюся непосредственным следствием этих формул. Правило вывода Modus Ponens обозначается через MP и записывается, как

MP

Формула A называется выводимой в исчислении L из формул X₁, X₂, …, X_k, если существует последовательность формул: A₁, A₂, A₃, …, A_n, такая, что для каждого формула A_i является либо аксиомой исчисления L, либо элементом множества {X₁, …, X_k} , либо непосредственным следствием формул A_p и A_q, при некоторых
1 p, q i-1. В этом случае последовательность: A₁, A₂, A₃, …, A_n называется выводом формулы A. Для обозначения выводимости формулы A в исчислении L из формул X₁, …, X_k применяется запись:

X₁, X₂, …, X_{k L} A .

Если для вывода формулы A достаточно аксиом, то А называется теоремой теории L, а выводимость из пустого множества формул записывается, как

_L А .

Лемма. Имеет место теорема _L А А.

Доказательство. Построим вывод формулы А А из аксиом (А1) – (А3) следующим образом:

А₁ будет аксиомой (А2) для формул А, B = (А А), С = А;

А₂ будет аксиомой (А1) для формул А, В = (А А);

получим:

А₁=(А ((А А) А)) ((А (А А)) (А А)),

А₂=А ((А А) А).

Применяя правило вывода MP , будем иметь непосредственное следствие формул A₂ и A₁:

А₃=(А (А А)) (А А).

Следующая формула получается из аксиомы (А1) подстановкой В = А:

А₄=А (А А).

Применяя правило вывода MP, получим:

А₅ = А А.

Последовательность формул: A₁, A₂, A₃, А₄, А₅ = (А А) является искомым выводом формулы А А.

Теорема о дедукции

Пусть Г – множество формул. Запись Г _L А означает, что существует конечная последовательность формул X_i Г, , такая, что X₁, X₂, …,X_{n L} A. Вместо Г {X} _L А будем писать Г, X _L А. Легко видеть, что из Г _L (А В) следует существование вывода Г, А _L В. Верно и обратное утверждение:

Теорема (о дедукции). Пусть Г – множество формул исчисления L; А и В – формулы, и пусть

Г, А _L В.

Тогда Г _L (А В). В частности, при пустом Г, из выводимости А _L В вытекает теорема: _L А В.

Доказательство. Пусть В₁, В₂, …, В_n = В – вывод формулы из формул, принадлежащих множеству Г {A}. Докажем с помощью индукции по i, что Г _L (А В_i), а затем применим это к i = n, чтобы получить Г _L (А В). При i = 1 имеем В₁ Г, либо В₁ = А, либо В₁ – аксиома. Если В₁ Г, либо В₁ – аксиома, тогда получаем с помощью аксиомы (А1) формулу В₁ (А В₁). Применение MP к В₁ и В₁ (A В₁) дает вывод для А В₁ из Г. Если же В₁ = А, то имеем: _L (А В₁) по доказанной лемме о том, что верна теорема _L А А.

Докажем теперь: Г _L (А В_i) при i > 1, предполагая, что выводимость
Г _L (А В_к) уже доказана для всех k < i.

Для В_i имеем 4 возможности: В_i Г; В_i – аксиома; В_i = А; В_i непосредственно следует из В_j и В_m, при некоторых j, m i-1. В первых трёх случаях Г _L А В_i доказывается так же, как при i = 1. В четвёртом случае формула В_m равна формуле (В_j В_i), и согласно предположению индукции имеем:

Г _L (А В_j) и Г _L (А (В_j В_i)),

ибо (В_j В_i)=В_m. По аксиоме (А2) верно

_L (А (В_j В_i)) ((А В_j) (А В_i)).

Применение

MP

приводит к выводу Г _L (А В_j) (А В_i). Из этого вывода и вывода Г
_L (А В_j) с помощью Modus Ponens получаем:

Г _L (А В_i).

Таким образом, Г _L (А В_i), для всех i = 1,…,n. В частности, при i = n, получаем:

Г _L (А В),

что и требовалось доказать.