Федеральное государственное автономное

образовательное учреждение

высшего профессионального образования

«СИБИРСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»

Институт космических и информационных технологий

Кафедра «Информатика и вычислительная техника»

 

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

Булевы функции и РКС

Дисциплина «Математическая логика»

Выполнил: Угадов А.И. студент 2 курса группа: КИ 12-11Б

   Проверил:

Красноярск   2013

Содержание:

1. Булевы функции.

   1. Булевы функции одной переменной.

   2. Булевы функции двух переменных.

   3. Булевы функции трех переменных.

2. Реализация функций формулами.

3. Законы булевой алгебры.

1. Идемпотентность.

2. Коммутативность.

3. Ассоциативность.  

4. Дистрибутивность. 

5. Закон поглощения.  

6. Закон склеивания.  

7. Закон нуля.              

8. Закон единицы.        

9. Закон дополнения. 

10.  Инволютивность.    

11.   Законы де Моргана. 

4. СКНФ.

5. СДНФ.

6. релейно-контактные схемы (РКС).

Введение:

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

Таким образом, теория булевых функций предоставляет математические модели реальных физических релейно-контактных схем.

В теории релейно-контактных схем различают две главные задачи – анализа и синтеза. Задача анализа состоит в изучении характера работы данной схемы и ее упрощения. Задача синтеза заключается в построении схемы с наперед заданными условиями работы.

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

Булевы функции находят применение в конструировании и упрощении логических схем. Такие схемы встречаются в электронных устройствах, используе­мых в компьютерах, калькуляторах, телефонных системах и ряде других устройств.

Обозначим множество {0;1} через  , т. е.. Булевой функцией от n аргументов называется отображение функция f из n-ой степени множества во множество

Т.е..

 Напомним, что -это множество наборовa = (a1,a2,...),где ={0,1}, i=1,2…n.

Переменные булевых функций могут принимать только значения 0 или 1 и называются булевыми переменными.

Булев вектор это последовательность булевых констант.

Примеры: α=a1a2…a6=010101, β = b1b2…b8= 11110000.

Множество всех булевых функций от любого числа аргументов часто обозначается P₂, а от n аргументов — P₂(n).

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

 .

Теорема (о числе булевых функций от аргументов). Число различных булевых функций от аргументов равно.

Доказательство. Чтобы задать булеву функцию отаргументов, нужно перечислить все наборыиз нулей и единиц значений, которые могут принимать ее аргументы, и для каждого такого набора указать значение функции, которое она принимает на этом наборе.

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

Например, булевы функции 1 переменной

,

булевых функции 2 переменных

,

 булевых функции 3 переменных

 .

Булевы функции часто задаются таблично. Эти таблицы напоминают таблицы истинности логических операций, поэтому сами булевы функции часто называют  булевыми операциями, а соответствующие им таблицы - таблицами истинности.

Булевы функции одной переменной

		Значения переменной   х	0	1
	Название функции	Обозначение функции	Значения  функции
f1	Тождественный нуль	0	0	0
f2	Тождественная	х	0	1
f3	Отрицание		1	0
f4	Тождественная единица	1	1	1

Булевы  функции двух переменных

		Значения   переменных	x1	0 0	0 1	1 0	1 1
			x2
	Название функции	Обозначение функции		Значения  функции
f1	Тождественный нуль	0		0	0	0	0
f2	Конъюнкция	&, ,·		0	0	0	1
f3	Отрицание импликации			0	0	1	0
f4	Тождественная первой переменной			0	0	1	1
f5	Отрицание импликации			0	1	0	0
f6	Тождественная второй переменной			0	1	0	1
f7	Сумма по модулю два, строгая дизъюнкция	,		0	1	1	0
f8	Дизъюнкция			0	1	1	1
f9	Стрелка Пирса			1	0	0	0
f10	Эквиваленция	,  ,  ~		1	0	0	1
f11	Инверсия второй переменной			1	0	1	0
f12	Импликация			1	0	1	1
f13	Инверсия первой переменной			1	1	0	0
f14	Импликация			1	1	0	1
f15	Штрих Шеффера			1	1	1	0
f16	Тождественная единица	1		1	1	1	1

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

 ,

(тождественная единица) и др.