Реферати українською » Математика » Подання булевих функцій в СКНФ


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

 

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

«Уявленнябулевих функцій вСКНФ»



Запровадження

У курсі дискретної математики вивчаються функції, область визначення яких – дискретне безліч.Простейшим (але нетривіальним) таким безліччю є безліч, що складається з двох елементів.


Теоретична частина

 

Теоретично дискретних функціональних систембулевой функцією називають функцію типу , де –булево безліч, а n – ненегативне ціла кількість, яку називаютьарностью чи місцевістю функції. Елементи 0 (нуль) і одну (одиниця) стандартно інтерпретують як і брехня, хоча у загальному разі їхній смисл може бути будь-якою. Елементи називаютьбулевими векторами. Що стосується 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>

>intOutputABC (>int a,int b,int з,int x,int y)

{

>cout << «(»;

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

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

>if (з == 1)cout << «~З»;elsecout << «З»;

>cout <<»)»;

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

y++;

>return(y);

};

>voidmain ()

{>constintK=8;constintN=3;

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

>i=0;

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

{

>cout << «>Vvediteznacheniefunkciinadannomnabore» <<endl;

>cin >>b[0] [j];

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

>cout <<endl << «>Fatalerror!!!Pleaseinputonly 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 Зfnn»;

>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]<<»nn»;

>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


Схожі реферати:

Навігація