Логические операции и выражения

Логические величины – это понятия, выраженные словами ИСТИНА или ЛОЖЬ. Следовательно, истинность высказываний выражается через логические величины.

Логические константы: ИСТИНА или ЛОЖЬ.

Логическая переменная – это символическое обозначение логической величины. Например, если известно, что А, В, С – это логические переменные, то они принимают значение только ИСТИНА или ЛОЖЬ.

Логическое выражение – простое или сложное высказывание. Сложное высказывание строится из простых с помощью логических операций.

Логические операции

Конъюнкция (логическое умножение) в русском языке выражается союзом «И». Конъюнкция обозначается знаком & или . Это двухместная операция; записывается в виде А В. Значение такого выражения будет ложно, если значение хотя бы одного операнда ложно.

Дизъюнкция (логическое сложение) в русском языке выражается союзом «Или». Дизъюнкция обозначается знаком . Это двухместная операция, записывается в виде А В. Значение такого выражения будет истинным, если значение хотя бы одного операнда истинно.

Отрицание в русском языке выражается частицей «НЕ». Это унарная (одноместная) операция, которая записывается в виде ⌐А или .

Импликация (условное высказывание) в русском языке выражается союзами «Если…то»; «Когда…тогда»; «Коль скоро…то» и т.п. Импликация обозначается знаком →. Это двухместная операция, записывается в виде А → В.

Эквивалентность в русском языке выражается союзами «Если и только если»; «Тогда и только тогда, когда». Эквивалентность обозначается знаком ↔.

Приведем таблицы истинности для рассмотренных логических операций.

A	B	A B	A B	`A	A «B	A ® B
0	0	0	0	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	0	0
1	1	1	1	0	1	1

В таблице значение ИСТИНА обозначено через 1, а значение ЛОЖЬ – 0.

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

Логическая формула (логическое выражение) – формула, содержащая лишь логические величины и знаки логических операций. Результатом вычисления логической формулы является ИСТИНА или ЛОЖЬ.

Пример 3.2. Определите истинность формулы

F = ((C B) → B) (A B) → B.

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

1.В заголовок таблицы выносятся все переменные в порядке их следования в формуле.

2.Если n –количество переменных, то строк в таблице будет 2 × n.

3. Первая колонка заполняется наполовину значением 1 (истина), наполовину 0 (ложь).

4. Последующие столбцы заполняются по правилу: первая половина значений 1 предыдущего столбца заполняется 1, вторая 0, так же и для 0.

5. В последнем столбце значения 1 и 0 чередуются.

C	B	A	C B	(C B) → B	A B	((C B) → B) (A B)	F
1	1	1	1	1	1	1	1
1	1	0	1	1	0	0	1
1	0	1	1	0	0	0	1
1	0	0	1	0	0	0	1
0	1	1	1	1	1	1	1
0	1	0	1	1	0	0	1
0	0	1	0	1	0	0	1
0	0	0	0	1	0	0	1

Ответ: Формула является тождественно истинной.

Логические схемы

Удобным способом представления логических выражений являются логические схемы. Вот как изображаются на таких схемах три основные логические операции:

Дизъюнкция	Конъюнкция	Отрицание

Эти схемы называются вентилями.

Алгоритм построения логических схем следующий.

1. Определите число логических переменных.

2. Определите количество базовых логических операций и их порядок.

3. Изобразите для каждой логической операции соответствующий ей вентиль.

4. Соедините вентили в порядке выполнения логических операций.

Пример 3.3. Нарисовать логическую схему выражения А В С.

Количество логических переменных равно 3. Количество базовых логических операций равно 2. Порядок выполнения операций в соответствии с приоритетом: сначала выполняется конъюнкция , а затем дизъюнкция .

Пример 3.4. Вычислить значение выражения  с помощью логической схемы. А = 0; В = 1; С = 1; D = 0.

Количество логических переменных равно 4. Количество базовых логических операций равно 4. Порядок выполнения операций: операция дизъюнкции В ˅ С , затем первая и вторая конъюнкции, последняя операция – отрицание.

Ответ: Значение выражения равно 1.

Пример3.5. Дана логическая схема. Построить соответствующее ей логическое выражение.

Строим таблицу входов и выходов каждого вентиля в соответствии с нумерацией.

Вентиль	Вход	Выход
1	А, В	А В
2	В, С	В С
3	А В; В С	(А В) (В С)
4	(А В) (В С)

Ответ: логическая схема реализует функцию .