Основные законы, определяющие свойства введенных логических операций

1) Идемпотентность дизъюнкции и конъюнкции:

X X↔X, X X↔X.

2) Коммутативность дизъюнкции и конъюнкции:

3) Ассоциативность дизъюнкции и конъюнкции:

4) Дистрибутивность операций дизъюнкции и конъюнкции относи­
тельно друг друга:

5) Двойное отрицание:

6) Закон де Моргана:

7) Склеивание:

.

8) Поглощение:

.

9) Действие с логическими константами 0 и 1:

, , , ,

10) Закон исключения третьего:

.

11) Тождество:

Х↔Х.

12) Отрицание противоречия:

.

13) Контрапозиция:

.

14) Цепное заключение:

.

15) Противоположность:

.

16) Модус поненс (modus ponens):

.

Сформулированные законы легко проверить с помощью таблицы истинности.

Заметим, что при исследовании различных высказываний на эквивалентность (равносильность) логическую связку ↔ можно заменить обычным знаком равенства =.

Задача. Составьте таблицу истинности формулы: .

Решение. Расставим скобки: .

X	Y	Z				ХфУ
]

Задача. Докажите тождественную истинность формулы .

Решение. Составим таблицу истинности:

X	Y

Последний столбец состоит из 1, следовательно, доказана тождественная истинность формулы.

Задача. Проверьте, будут ли эквивалентны следующие формулы:

а) ; б)

Решение. Составим таблицы истинности:

X	У	Z	Y@z	X -> (У (В Z)

Формулы не эквивалентны.

X	У	Z	Y^Z

Формулы эквивалентны.

Булева функция, или функция алгебры логики, является одним из основных объектов дискретной математики.

Функцию f(x₁, x₂,…,х_п), принимающую одно из двух значений 0 или 1, от п переменных, каждая из которых принимает одно из двух значений О или 1, будем называть булевой функцией f(x₁, x₂,…,х_п) от п переменных.

Булева функция от п переменных сопоставляет каждому упорядо­ченному набору (кортежу), составленному из п элементов, 0 и 1, либо 1, либо 0.

Две булевы функции называются равными, если для любых одинаковых наборов значений переменных обе функции принимают одинаковые значения. Булевых функций одной переменной четыре, а двух переменных — шестнадцать и т. д. Число булевых функций от п переменных равно 2²ⁿ.

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

Таблица истинности булевой функции одной переменной:

X	f1(x)	f2(x)	f3(x)	f4(x)

Функции f₁(x) и f₄(x) называются константами — соответственно 0 и1.

Функция f₂(x) совпадает с переменной х и называется тождественной f₂(x) = х:

Функция f₃(x) принимает значения, противоположные значениям аргумента х, и называется отрицанием х, обозначается х: f₃(x) = .

Таблица истинности булевой функции двух переменных:

x1

х2

f1

f2

f3

f4

f5

f6

f7

f8

f9

f10

f11

f12

f13

f14

f15

f16

i

l

l

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

1. Функции f₁ и f₁₆ представляют собой константы 0 и 1.

2. Функции f₄, f₆ , f_11,f₁₃ существенно зависят только от одной переменной: f₄=x₁,. f₆=x₂, f₁₁= , f₁₃=

3. Остальные функции существенно зависят от двух переменных, и для них есть названия и обозначения:

а) функция называется конъюнкцией,

б) функция называется дизъюнкцией,

в) функция называется эквивалентностью,

г) функция называется суммой по модулю два, или суммой Жегалкина,

д) функция / называется конверсией,

е) функция называется импликацией,

ж) функция называется штрих Шеффера,

з) функция называется стрелкой Пирса,

и) функции логически несовместимы с импликацией и конверсией и называются функциями запрета.

Дата добавления: 2014-11-07