Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364141
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62791)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21692)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8693)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3462)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20644)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

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

Название: Представление булевых функций в СКНФ
Раздел: Рефераты по математике
Тип: курсовая работа Добавлен 15:04:37 23 апреля 2011 Похожие работы
Просмотров: 978 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

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

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


Введение

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

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

В теории дискретных функциональных систем булевой функцией называют функцию типа , где – булево множество, а 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

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений08:04:44 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
10:31:39 29 ноября 2015

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

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(173704)
Комментарии (1984)
Copyright © 2005-2017 BestReferat.ru bestreferat@gmail.com реклама на сайте

Рейтинг@Mail.ru