Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (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)
Иностранный язык (62792)
Информатика (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)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

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

Название: Представление булевых функций в СКНФ
Раздел: Рефераты по математике
Тип: курсовая работа Добавлен 15:04:37 23 апреля 2011 Похожие работы
Просмотров: 808 Комментариев: 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

Работы, похожие на Курсовая работа: Представление булевых функций в СКНФ
Объектно-ориентированное программирование на Borland C++
Объектно-ориентированное программирование на Borland C++ Тексты лекций, прочитанных в Московском государственном университете экономики, статистики и ...
int i, j, k; // Три переменных типа int без явной инициализации
Для правильного вывода требуется, чтобы переменная x была типа int, y - типа float, а переменная st - типа char*.
Раздел: Рефераты по информатике, программированию
Тип: учебное пособие Просмотров: 914 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Основы дискретной математики
Федеральное агентство по образованию Новомосковский институт (филиал) Государственного образовательного учреждения высшего профессионального ...
Элемент массива EXT-NAME(j) содержит внешнее имя множества, внутреннее имя которого есть j, а INT-NAME(k) - внутреннее имя множества, внешнее имя которого есть к.
B:=INT-NAME(j);
Раздел: Рефераты по информатике, программированию
Тип: учебное пособие Просмотров: 4174 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Object Pascal
... Основными символами языка Object Pascal являются: - символы _ - 26 больших и 26 малых латинских букв A,B, .Y,Z, a,b, ., y,z - 10 арабских цифр 0, 1, 2 ...
Здесь x - переменная, y - выражение.
Процедура c именем ByRef содержит три параметра - переменную X и две константы L и K. Тело процедуры состоит из операторов, заключенных в операторных скобках begin - end.
Раздел: Рефераты по информатике
Тип: реферат Просмотров: 2123 Комментариев: 4 Похожие работы
Оценило: 2 человек Средний балл: 4 Оценка: неизвестно     Скачать
Основы C
Кафедра: Автоматика и Информационные Технологии ОСНОВЫ С ОГЛАВЛЕНИЕ Введение Глава 1. Основы языка Си 1.1. Алфавит 1.2. Основные конструкции Си 1.3 ...
{ int t,a,b,x,y;
{ int m,n,i,j,k,a[mm],b[nn],c[mm+nn];
Раздел: Рефераты по информатике, программированию
Тип: учебное пособие Просмотров: 1162 Комментариев: 2 Похожие работы
Оценило: 1 человек Средний балл: 5 Оценка: неизвестно     Скачать
Конспект лекций по дискретной математике
Приложение Булевой алгебры к синтезу комбинационных схем Двоичная система логики: 1. Элементы Булевой алгебры: а) числа b) переменные с) операции d ...
Нормальные формы строятся на основании операций конъюнкции, дизъюнкции и отрицания, причем отрицание только единственной переменной.
В связи с тем, что любую сколь угодно сложную Булеву функцию можно представить в канонических формах, то есть записать ее с помощью операций отрицания, конъюнкции и дизъюнкции эта ...
Раздел: Рефераты по математике
Тип: реферат Просмотров: 1650 Комментариев: 4 Похожие работы
Оценило: 2 человек Средний балл: 2 Оценка: неизвестно     Скачать
Дискретная математика
Министерство образования и науки Российской Федерации Российский химико-технологический университет им. Д.И. Менделеева Новомосковский институт ...
Пусть функция X=F (A, B, C) задана таблицей 4. Запись функции Х в виде логической суммы (дизъюнкции) логических произведений (конъюнкций) переменных, для которых значение функции Х ...
Мы уже видели, что любая булева функция реализуется через конъюнкцию, дизъюнкцию и отрицание.
Раздел: Рефераты по математике
Тип: учебное пособие Просмотров: 5203 Комментариев: 2 Похожие работы
Оценило: 1 человек Средний балл: 2 Оценка: неизвестно     Скачать
Исследование движения центра масс межпланетных космических аппаратов
2. ИССЛЕДОВАТЕЛЬСКАЯ ЧАСТЬ 2.1. ВВЕДЕНИЕ В данной работе проводится исследование движения центра масс МКА под действием различных возмущающих ...
} void out_p(real x,real *y,real*,int,int,real*)
set(plt,'xdata',x(k),'ydata',y(k),'zdata',z(k))
Раздел: Рефераты по астрономии
Тип: реферат Просмотров: 312 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Основы алгоритмического языка С++
Переменные и операции языка С++ Здесь представлены базовые компоненты программ на С++. В их число входят типы данных, переменные, константы и ...
A B C D E F G H I J K L M N O P Q R T U V W X Y Z
В первом примере объявляется простая переменная x. Эта переменная может принимать любое значение из множества значений, определяемых для типа int.
Раздел: Рефераты по информатике, программированию
Тип: реферат Просмотров: 682 Комментариев: 5 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

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

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

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



Результаты(150887)
Комментарии (1841)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru