Зависимости между булевыми функциями

1.Соотношение между константами

0 = , 1 = , x = ù .

Для функций двух переменных

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

1. Отрицание «Не Х»

2. Константы 0 или 1

3. Конъюнкцию или штрих Шеффера

4. Импликацию или ее отрицание

5. Эквивалентность или неравнозначность

6. Дизъюнкцию или стрелку Пирса.

Кроме этого импликация может быть выражена через дизъюнкцию и отрицание

а эквиваленциячерез конъюнкцию, дизъюнкцию и отрицание

	Æ	Æ
	Æ		Æ
			Æ	Æ
		Æ		Æ
			Æ
		Æ
		Æ	Æ	Æ

В результате комплект элементарных функций сократился до четырех:

1. Константы нуля и единицы

2. Отрицание

3. Дизъюнкция

4. Конъюнкция.

Этот комплект более удобен и на практике принимается больше всего, но может быть сокращен. Поскольку по законам де Моргана и свойству двойного отрицания: , ,

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

Это вытекает из следующих соотношений:

.

Прикладное значение последних операций: при реализации технологических процессов, сложных логических функций достаточно настроить технологический процесс получение одного вида из таких логических операций, а затем соответствующей коммутацией полупроводниковых слоёв получать функции любой сложности.

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

1. Переместительный или коммутативный:

.

2. Сочетательный или ассоциативный:

3. Распределительный или дистрибутивный:

4. Закон инверсии или де Моргана:

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

а)б)

в)

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

7. Закон обобщенного склеивания:

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

1.Закон противоречия:

2. Закон исключенного третьего:

3. Закон двойного отрицания:

4. Законы идемпотентности:

Тождества булевой алгебры

5.

6.

7.

8.

9. .

При решении логических выражений устанавливают следующий приоритет выполнения операций:

1. Отрицание

2. Конъюнкция

3. Дизъюнкция

4. Импликация

5. Эквиваленция.

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

Высказывания

Известно, что множества задают двумя способами: перечислением иописанием. Описательный способ связывает учение о множествах с учением, о высказываниях, которое составляет часть математической логики. Высказыванием называют любое утверждение, которое может быть истинным или ложным. Рассмотрим высказывания по отношению к элементам некоторого универсального множества I так как разные элементы обладают разными свойствами, то есть составляют разные группы подмножеств.

Например:

I – электрорадиоэлементы,

M – микросхемы, подмножество I,

T - транзисторы, подмножество I,

M и T - составляют множество истинности.

Существуют простые и составные высказывания, обозначаются строчными буквами латинского алфавита. Если высказывание истино то ему присваивают 1, если ложно 0. Высказывания, которым соответствуют простые множества истиности, называют простыми высказываниями.

Пример:

m₁ - микросхема Î M,

t₁ - транзистор Î T.

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

Пример:

M – множество микросхем,

N - множество микросхем в приемнике,

Q = M Ç N ¾ множество микросхем в приемнике,

q Î Q ¾ множество микросхем в приемнике,

q - высказывание,

Q - составное подмножество.

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