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


Полнотекстовый поиск по базе:

Главная >> Курсовая работа >> Математика


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




Курсовая работа

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

Введение

В курсе дискретной математики изучаются функции, область определения которых – дискретное множество. Простейшим (но нетривиальным) таким множеством является множество, состоящее из двух элементов.

Теоретическая часть

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

Каждая булева функция арности n полностью определяется заданием своих значений на своей области определения, то есть на всех булевых векторах длины n. Число таких векторов равно 2n. Поскольку на каждом векторе функция может принимать значение либо 0, либо 1, количество всех n-арных булевых функций равно . То, что каждая булева функция задаётся конечным массивом данных, позволяет представлять их в виде таблиц. Такие таблицы носят название таблиц истинности и в общем случае имеют вид:

x1

x2

xn

f(x1, x2,…, x1)

0

0

0

f (0,0,…, 0)

1

0

0

f (1,0,…, 0)

0

1

0

f (0,1,…, 0)

1

1

0

f (1,1,…, 0)

0

1

1

f (0,1,…, 1)

1

1

1

f (1,1,…, 1)

Нульарные функции

При n = 0 количество булевых функций сводится к двум, первая из них тождественно равна 0, а вторая 1. Их называют булевыми константами.

При n = 1 число булевых функций равно . Им соответствуют следующие таблицы истинности.

x

g1 ()

g2 (=)

g3 (1)

g4 (0)

0

1

0

1

0

1

0

1

1

0

Здесь:

g1 (x) – отрицание (обозначения: ),

g2 (x) – тождественная функция,

g3 (x) и g4 (x) – соответственно, тождественная истина и тождественная ложь.

Бинарные функции

При n = 2 число булевых функций равно . Им соответствуют следующие таблицы истинности.

x

y

f1 ()

f2 ()

f3 ()

f4 ()

f5 ()

f6 ()

f7 ()

f8 ()

0

0

0

0

1

0

1

1

1

1

0

1

0

1

0

1

0

1

0

1

1

0

0

1

0

1

1

0

0

1

1

1

1

1

1

0

1

1

0

0

x

y

f9

f10

f11

f12

f13

f14

f15

f16

0

0

0

0

1

1

0

0

1

0

0

1

0

1

1

0

0

1

1

0

1

0

1

0

0

1

1

0

1

0

1

1

0

0

0

0

1

1

1

0

Здесь:

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

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

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

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

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

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

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

f8 (x, 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) – тождественная истина и тождественная ложь.

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

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

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

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

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

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

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

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

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

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

Алгоритм

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

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++)

{

cout << «Vvedite znachenie funkcii na dannom nabore» << endl;

cin >> b[0] [j];

while (! (b[0] [j] == 1 || b[0] [j] == 0))

cout << endl << «Fatal error!!! Please input only 0 or 1» << endl, cin >> 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

Похожие работы:

  • Булевы функции

    Контрольная работа >> Математика
    ... представлений и множеством схем, реализующих булеву функцию, существует взаимно однозначное соответствие, отыскание канонической формы представления булевой функции ...
  • Представление логических функций от большого числа переменных

    Дипломная работа >> Информатика, программирование
    ... функции, кроме константы 0, таким представлением может служить её СДНФ. Константу 0 можно представить булевой ... 1 1 0 1 1 1 1 1 Таким образом получаем следующую СКНФ: f(x,y,z)=(хyz)^(xy z)^(x yz)^( x y z) Разрешимoсть задач в классической теории ...
  • Функции алгебры логики. Логический базис

    Реферат >> Коммуникации и связь
    ... с помощью законов и правил Булевой алгебры. При табличном способе ФАЛ ... виде: , (3) то форма представления данной функции не является СДНФ, так ... аргументы функции либо их инверсии. Запишем функцию в СКНФ: . (6) По функциям, представленным в СДНФ и СКНФ, можно ...
  • Дискретная математика

    Учебное пособие >> Математика
    ... имеет вид: . (3) Для представления логической функции Х в СКНФ произведем операцию отрицания левой и правой ... функции F было минимальным. 3.10 Формы представления булевых функций К настоящему времени мы знакомы с двумя формами представления булевых функций ...
  • Математическая логика

    Контрольная работа >> Математика
    ... Двойственное предельное разложение Шеннона булевой функции является ее СКНФ. 2 Булевы функции двух переменных Рассмотрим ... в которых булева функция принимает единичные значения, получим геометрическое представление булевой функции. Так функция примет вид ...
  • Синтез логической функции и анализ комбинационных схем

    Реферат >> Радиоэлектроника
    ... отримані логічні функції використовуючи карти Карно та закони булевої алгебри: _ _ _ ... _ _ СДНФ: f=x1x3x4(x2x2)x1x2x3x4=x1x3x4x1x2x3x4 СКНФ: ... ється пошук коротких форм представлення, перемикаючих функцій для скорочення числа фізичних ...
  • Логическое и функциональное программирование

    Учебное пособие >> Информатика, программирование
    ... и СКНФ. x y z f 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 0 СДНФ: СКНФ: Минимизация булевых функции Под минимизацией булевых функций понимается нахождение наиболее простого представления этой функции в виде ...
  • Основы анализа и синтеза комбинационных логических устройств

    Учебное пособие >> Информатика, программирование
    ... 1 1 0 1 1 2. Алгебраическое представление логической функции в СДНФ 3. Алгебраическое представление логической функции в СКНФ Ускорить процесс нахождения ... x+1=1 xx=x x+x=x Таблица 1.7 Законы булевой алгебры Закон булевой алгебры Конъюнкция Дизъюнкция 1 2 3 ...
  • Компьютерная схемотехника

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

    Курсовая работа >> Информатика, программирование
    ... функциональные схемы . а) СДНФ б) СКНФ Рис. 1.1 Функциональная схема полусумматора . ... или заполняются 0. Примеры графического представления функций, заданных в виде СДНФ, ... таблицу истинности в выражение булевой логики; - выражение булевой логики в схему или ...