выш мат. Алексеев-В.В.-Алгебра-логики. Инистерство образования и науки российской федерации

• Название: Инистерство образования и науки российской федерации
• Анкор: выш мат
• Дата: 14.03.2020
• Размер: 6.59 Mb.
• Имя файла: Алексеев-В.В.-Алгебра-логики.doc
• Тип: Методическое пособие; #111937
• страница: 2 из 9

В силу теоремы 1.2 имеем 10 различных функций, существенно зависящих от аргументов и . Из них рассмотрим семь, которые играют большую роль в построении теории ФАЛ и ее приложениях. (Помимо рассмотренных 1.5 и 1.6).
а). Функция  = ==& конъюнкция (логическое умножение, или функция И) истинна тогда и только тогда, когда и и истинны.

		
0	0	0
0	1	0
1	0	0
1	1	1

б). Функция  =  - дизъюнкция (логическое сложение, или функция ИЛИ) истинна тогда, и только тогда, когда истинны или , или , или обе переменные.

		
0	0	0
0	1	1
1	0	1
1	1	1

в). Функция  = ( ) Функция сложения по модулю 2 (или функция разноименности, или функция исключающее ИЛИ) истинна тогда, когда истинна или , или , но не обе вместе.

		
0	0	0
0	1	1
1	0	1
1	1	0

г).Функция - ) функция равнозначности, которая истинна тогда и только тогда, когда обе переменные или истинны, или ложны.

		
0	0	1
0	1	0
1	0	0
1	1	1

д.) Функция  = () (импликация в ), которая ложна тогда и только тогда, когда истинна, а ложна

		=	=
0	0	1	1
0	1	1	0
1	0	0	1
1	1	1	1

.
е.) Функция - функция Пирса ( Вебба ), которая истинна тогда и только тогда, когда и ложны.

		
0	0	1
0	1	0
1	0	0
1	1	0

ж.) Функция  = (/) (Функция Шеффера), которая ложна только тогда, когда и истинны.

		
0	0	1
0	1	1
1	0	1
1	1	0

Для наглядности рассмотренные функции сведены в общую таблицу:

		&							/
0	0	0	0	0	1	1	1	1	1
0	1	0	1	1	0	1	0	0	1
1	0	0	1	1	0	0	1	0	1
1	1	1	1	0	0	1	1	1	0

Рассмотренные 11 функций алгебры логики называются элементарными и позволяют строить новые ФАЛ двумя основными путями:

1. Путем перенумерации аргументов (для некоторых функций)

2. Путем подстановки в функцию новых функций вместо аргументов.

Функцию, полученную из функций путем применения (возможно многократного) этих двух правил, называют суперпозицией функций .
1.3 Свойства элементарных ФАЛ.
Из рассмотренных определений ФАЛ видно, что все они находятся в определенной взаимосвязи друг с другом. Используя основные положения АЛ, нетрудно убедиться в справедливости следующих восьми аксиом. Пусть x - некоторая логическая переменная. Тогда:

1.	=x	(Означает возможность исключение из логического выражения всех членов, имеющих двойное отрицание, заменив их исходной величиной x).
2.	xx=x xx=x	Эти правила позволяют сократить длину логических преобразований).

3. x0=x

4. x1=1

5. x0=0

6. x1=x (1.7)

7. x=0

8. x=1
1.3.1 Выражение одних элементарных функций через другие.
Установим ряд формул, которые в дальнейшем будут широко применяться. Для доказательства всех формул будем пользоваться единообразным методом. Этот метод заключается в непосредственной проверке совпадения функций, образующих правую и левую часть доказываемых соотношений (См. определение 6)

1. = (1.8)

0	0	1		0	0	1	1
0	1	1		0	1	1	1
1	0	0		1	0	0	0
1	1	1		1	1	0	1

2. = (1.9 )

0	0	0		0	0	1	0
0	1	1		0	1	0	1
1	0	1		1	0	0	1
1	1	0		1	1	1	0

3. = (1.10)

0	0	1		1	1	1	1	1
0	1	0		1	0	1	0	0
1	0	0		0	1	0	1	0
1	1	1		0	0	1	1	1

4. = (1.11)

0	1	0
1	0	1

5. (1.12)
Справедливость этой формулы вытекает из (1.9) и (1.10.)
6. = (1.13)

0	0	0		0	0	1	1	1	0
0	1	0		0	1	1	0	1	0
1	0	0		1	0	0	1	1	0
1	1	1		1	1	0	0	0	1

7. = (1.14)

0	0	0		0	0	1	1	1	0
0	1	1		0	1	1	0	0	1
1	0	1		1	0	0	1	0	1
1	1	1		1	1	0	0	0	1

Выражения (1.13) и (1.12) известны как правила де Моргана.

Аналогично можно установить ряд взаимоотношений между другими функциями алгебры логики.

Теперь, используя установленные “взаимоотношения” между элементарными ФАЛ и аксиомы алгебры логики, можно аналитически выразить одни ФАЛ через другие. Например, используя “табличный метод” доказательства, было установлено: . Тогда справедливо отношение: . Учитывая, что , получаем следующее выражение: .

Аналогично, используя правила де Моргана получаем следующее выражение для функции сложения по модулю два:


1.3.2 Свойства конъюнкции, дизъюнкции, отрицания

Функции конъюнкции (функция И), дизъюнкции (функция ИЛИ) обладают рядом свойств, аналогичным свойствам обычных операций умножения и сложения. Для них справедливы:

1. Свойство ассоциативности (сочетательный закон):

.

.

2. Свойство коммутативности (переместительный закон):

.

.

3. Свойство дистрибутивности (распределительный закон):

• 
  для конъюнкции относительно дизъюнкции:
  

.

• 
  для дизъюнкции относительно конъюнкции:
  

.

Действительно:

.

Обобщение формул (1.13) и (1.14) позволяет получить формулы, известные как законы Де-Моргана:

. (1.15)

. (1.16)

Из логических функций устанавливаются соотношения, известные как законы (правило) поглощения:

;

.

Доказательство этих соотношений не вызывает затруднений. Например, для первого соотношения имеем: .

Второе соотношение доказывается аналогично:

.

Из логических функций устанавливается правило склеивания:

Также для логических функций установлено правило вычеркивания:

.

Действительно:

Знание свойств, законов и правил элементарных ФАЛ необходимо для аналитического описания функций алгебры логики, их преобразований.