Быстрый поиск

Курсовая работа: Представление булевых функций в СКНФ

f1 (x, y) – конъюнкция (обозначения: x&y, $x\cdot y, x y, x\land y$ ),

f2 (x, y) – дизъюнкция (обозначение: $x \lor y$ ),

f3 (x, y) – эквивалентность (обозначения: $x\sim y, x\equiv y, x\leftrightarrow y$ ),

f4 (x, y) – исключающее «или» (сложение по модулю 2; обозначения: $x \oplus y, x+y$ ),

f5 (x, y) – импликация от y к x (обозначения: $x\leftarrow y, x \subset y$ ),

f6 (x, y) – импликация от x к y (обозначения: $x\rightarrow y, x\supset y$ ),

f7 (x, y) – стрелка Пи́рса (функция Да́ггера, функция Ве́бба, антидизъюнкция; обозначение: $x\downarrow y$ ),

f8 (x, y) – штрих Ше́ффера (антиконъюнкция; обозначение: $x \mid y$ ),

f9 (x, y) – отрицание импликации f6 (x, y),

f10 (x, y) – отрицание импликации f5 (x, y),

f11 (x, y) = g1 (x),

f12 (x, y) = g1 (y),

f13 (x, y) = g2 (x),

f14 (x, y) = g2 (y),

f15 (x, y), f16 (x, y) – тождественная истина и тождественная ложь.

Дизъюнктивная нормальная форма (ДНФ)

Простой конъюнкцией, или конъюнктом, называется конъюнкция некоторого конечного набора переменных, или их отрицаний, причём каждая переменная встречается не более одного раза. Дизъюнктивной нормальной формой или ДНФ называется дизъюнкция простых конъюнкций. Например $a \overline{b} c\lor b c\lor\overline{a}$ – является ДНФ.

Совершенной дизъюнктивной нормальной формой, или СДНФ относительно некоторого заданного конечного набора переменных называется такая ДНФ, у которой в каждую конъюнкцию входят все переменные данного набора, причём в одном и том же порядке. Например: $a \overline{b} c\lor a b c\lor\overline{a} b\overline{c}$ .

Легко убедится, что каждой булевой функции соответствует некоторая ДНФ, и даже СДНФ. Для этого достаточно взять таблицу истинности этой функции и найти все булевы векторы, на которых её значение равно 1. Для каждого такого вектора $b=(b_1,b_2,\ldots,b_n)$ строится конъюнкция $x_1^{b_1} x_2^{b_2}\ldots x_n^{b_n}$ , где $x_i^0 = \overline{x_i}$ . Если взять дизъюнкцию этих конъюнкций, то результатом очевидно будет СДНФ. Поскольку на всех булевых векторах её значения совпадают со значениями исходной функции, она будет СДНФ этой функции. Например, для импликации $x\to y$ , результатом будет $\overline{x} y \lor \overline{x}\, \overline{y}\lor x y$ , что можно упростить до $\overline{x}\lor y$ .

Конъюнктивная нормальная форма (КНФ)

Конъюнктивная нормальная форма (КНФ) определяется двойственно к ДНФ. Простой дизъюнкцией или дизъюнктом называется дизъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная входит в неё не более одного раза. КНФ – это конъюнкция простых дизъюнкций.

Совершенной конъюнктивной нормальной формой (СКНФ), относительно некоторого заданного конечного набора переменных, называется такая КНФ, у которой в каждую дизъюнкцию входят все переменные данного набора, причём в одном и том же порядке. Поскольку (С) КНФ и (С) ДНФ взаимодвойственны, свойства (С) КНФ повторяют все свойства (С) ДНФ, грубо говоря, «с точностью до наоборот».

КНФ может быть преобразована к эквивалентной ей ДНФ, путём раскрытия скобок по правилу:

$a (b\lor c)\to a b\lor a c$

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

$a\lor b c\to (a \lor b)(a \lor c)$

выражающее дистрибутивность дизъюнкции относительно конъюнкции. Результат нужно преобразовать способом, описанным выше, заменив слово «конъюнкция» на «дизъюнкция» и наоборот.

Алгоритм

Алгоритм получения СКНФ:

1. Получить таблицу истинности для определенного количества переменных;

2. Заполнить значения функции для каждого из наборов таблицы истинности;

3. Отметить те строки таблицы истинности, на которых функция приняла значение 0;

4. Выписать для каждой отмеченной строки дизъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке =0, то в дизъюнкцию включают саму переменную, если =1, то ее отрицание;

5. Все полученные дизъюнкции связать в конъюнкцию;

Листинг программы

#include <iostream.h>

#include <conio.h>

int OutputABC (int a, int b, int c, int x, int y)

{

cout << «(»;

if (a == 1) cout << «~Av»; else cout << «Av»;

if (b == 1) cout << «~Bv»; else cout << «Bv»;

if (c == 1) cout << «~C»; else cout << «C»;

cout <<»)»;

if (y<x-1) cout << «*»,

y++;

return(y);

};

void main ()

{const int K=8; const int N=3;

int i, j, b[N] [K], x(0), y(0);

i=0;

for (j=0; j<K; j++)

>> b[0] [j];

cout << endl;

i=1;

for (j=0; j<K; j+=2)

b[i] [j]=0;

for (j=1; j<K; j+=2)

b[i] [j]=1;

i=2;

for (j=0; j<K; j+=4)

b[i] [j]=0;

for (j=1; j<K; j+=4)

b[i] [j]=0;

for (j=2; j<K; j+=4)

b[i] [j]=1;

for (j=3; j<K; j+=4)

b[i] [j]=1;

i=3;

for (j=0; j<4; j++)

b[i] [j]=0;

for (j=4; j<K; j++)

b[i] [j]=1;

for (j=0; j<K; j++)

if (b[0] [j] == 0) x++;

cout<< «A B C f\n\n»;

cout<<«0 0 0 «<<b[0] [0]<<»\n0 0 1 «<<b[0] [1]<<»\n0 1 0 «<<b[0] [2]

<<»\n0 1 1 «<<b[0] [3]<<»\n1 0 0 «<<b[0] [4]<<»\n1 0 1 «<<b[0] [5]

<<»\n1 1 0 «<<b[0] [6]<<»\n1 1 1 «<<b[0] [7]<<»\n\n»;

cout<< «F=»;

for (j=0; j<K; j++)

if (b[0] [j] == 0)

y=OutputABC (b[3] [j], b[2] [j], b[1] [j], x, y);

getch();

}

Тестирование программы

входные данные:

результат:

входные данные:

результат:

Заключение

булева функция программа переменная

В курсовой работе был реализован алгоритм представления булевых функций в СКНФ.

По данному алгоритму на языке С++ была написана программа, результат которой был продемонстрирован.

Список использованной литературы

1. Яблонский С.В. Введение в дискретную математику. – М.: Наука. – 1986

2. Н.А. Ахметова, З.М. Усманова Дискретная Математика Функции алгебры логики учебное электронное издание – Уфа – 2004

Страницы: 1, 2, 3

Меню

Быстрый поиск

Курсовая работа: Представление булевых функций в СКНФ

Новости

Быстрый поиск

Группа вКонтакте: новости

Новости в Twitter и Facebook

Новости

Обратная связь