Логические функции одной переменной.

х	0	1	2	3
0	0	0	1	1
1	0	1	0	1

Функции ₀ и ₃ константы 0 и 1 соответственно, их значения не зависят от значения переменной х, а, следовательно, х – несущественная переменная.

Функция ₁ – тождественная функция. ₁ (х)=х.

Ф ункция ₂ – отрицание х ( функция НЕ ). ₂ (х)=х.

Логические функции двух переменных.

x	y	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

Функции ₀ , ₁₅ константы 0 и 1 соответственно.

Функция 1 – логическое умножение, конъюнкция (функция и).

Обозначается: xy,xy,xy.

Функция истинна (равна 1) только если значения обеих переменных истинны, в остальных случаях она ложна.

Функция ₇ – логическое сложение, дизъюнкция (функция ИЛИ).

Обозначается: x+y, xy.

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

Функция ₆ - сложение по модулю 2, жегалкино сложение.

Обозначается: хy.

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

Функция ₉ – эквивалентность, равнозначность.

Обозначается: xy,xy.

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

Функция ₁₃ – импликация, функция следования.

Обозначается: xy.

Функция ложна, когда х – истинна, а y – ложна.

Функция ₈ – стрелка Пирса.

Обозначается: xy.

Функция ₁₄ – штрих Шеффера.

Обозначается: xy.

Также логические функции можно задавать формулой.

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

F={f₁,f₂,...,f_m}. Множество F называется базисом.

Определение:

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

2. Если f(х₁,х₂, ... ,х_n)F и F₁, F₂,..., F_n – либо формулы, либо переменные, то выражение f(F₁, F₂, ... ,F_n) называется формулой над F.

3. Только те выражения являются формулами над F, которые могут быть получены из пунктов 1., 2.

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

Пример 1:

(хy)z

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

Пример 2:

С помощью таблицы истинности установите, эквивалентны ли данные формулы:

Решение:

Построим таблицу истинности для формул:

x	y	z	pq	(pq)r		x	y	z	pq
0	0	0	0	0		0	0	0	1	1
0	0	1	0	0		0	0	1	1	0
0	1	0	1	0		0	1	0	1	1
0	1	1	1	1		0	1	1	1	0
1	0	0	1	0		1	0	0	0	1
1	0	1	1	1		1	0	1	0	1
1	1	0	0	0		1	1	0	1	1
1	1	1	0	0		1	1	1	1	0

Формулы не являются эквивалентными, т.к. их значения противоположны на наборах 0,2,3,4,6.