Файл: Методические указания для проведения практических работ по профессиональному модулю Проектирование цифровых устройств.docx

Дизъюнкция (логическое сложение, от disunctio - разность). Дж. Буль ввел ее как сложение классов. Дизъюнкция является простейшей логической операцией и соответствует союзу «ИЛИ» и имеет два варианта действия, то есть соответствует двум операциям. Следует различать неисключающее «ИЛИ» (нестрогое логическое сложение) и исключающее "ИЛИ" (строгое логическое сложение).

Логическая операция, соответствующая неисключающему «ИЛИ» называется просто дизъюнкцией и соответствует связке (союзу) ИЛИ и обозначается АvВ или А+В (читается: "А или В"). Она определяется следующей таблицей истинности.

А	В	AvB
0	0	0
0	1	1
1	0	1
1	1	1

Таким образом, сложное высказывание A v В (логическая сумма) ложно в том и только том случае, когда оба высказывания А и В являются ложными.

Например, пусть высказывание А – «число 20 делится на 7» а В – «число 20 больше числа 7» Тогда сложное высказывание AvВ будет истинным, так как истинно высказывание В. Понятию дизъюнкции в математике соответствует понятие совокупности - если заданы, например, два уравнения f₁(x) = 0 и f₂(x) = 0

то совокупность уравнений

f

₁(x) = 0

f₂(x) = 0

будет иметь решения х, при которых выполняется (истинно) хотя бы одно уравнение. Совокупность уравнений в математической литературе иногда вместо квадратных скобок так и обозначается с использованием знака дизъюнкции - v

f₁(x) = 0 v f₂(x) = 0.

Исключающее ИЛИ

Логическая операция, соответствующая исключающему ИЛИ называется
исключающей дизъюнкцией (от «eXclusive OR, строгое логическое ИЛИ, строгое
логическое сложение, неэквивалентность) и соответствует союзу ЛИБО и обозначается AVB или А

В. (читается: “A плюс В”). Она определяется следующей
таблицей истинности.

А	В	AVB
0	0	0
0	1	1
1	0	1
1	1	0

Рассмотрим два примера поясняющие дизъюнкцию - неисключающее «ИЛИ» исключающее «ИЛИ»:

А) «Петров является программистом или Сидоров является студентом»;

Б) «Петров является программистом либо Сидоров не является студентом».

Если ввести высказывание Р – «Петров является программистом»,

С –«Сидоров является студентом». Тогда сложное высказывание А) можно записать символически - Р + С, а высказывание Б) можно записать символически Р

С,

Замечание. Логическую операцию А

В часто называют выбором альтернативы или логическим сложением по модулю два. Ее значения равны остатку при сложении натуральных чисел по модулю 2. Сложением натуральных чисел но некоторому модулю является представление суммы в виде остатка от ее деления на данный модуль, которое иногда называют жегалкинским сложением (в честь русского математика и логика И.И.Жегалкина).

Импликация

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

В или А

В. По определению импликация А

В истинна всегда, за исключением случая, когда А истинно, а В ложно. Таблица истинности для импликации имеет следующий вид:

А	В	А В
0	0	1
0	1	1
1	0	0
1	1	1

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

Например, А) Если 2 + 3 = 1, то 2

2 = 4.

Б) Если 2+ 3=4, то 2

2 = 5.

Очень часто высказывание, стоящее после слова "Если", называется основанием или посылкой, а стоящее после слова "то", называется следствием или заключением. Например, "Если идет дождь, то земля мокрая". Здесь простое высказывание "идет дождь" – основание, а следствие - "земля мокрая''.

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

Эквиваленция (эквивалентность, двойная импликация, от acquivalens — равноценное) является также простейшей логической операцией. Эквиваленция обозначается А

В или А

В. Сложное высказывание А

В (читается: А эквивалентно В) истинно тогда и только тогда, когда А истинно и В истинно либо А ложно и В ложно. В остальных случаях А

В ложно. Эквиваленция задается следующей таблицей истинности.

А	В	А В
0	0	1
0	1	0
1	0	0
1	1	1

Таким образом, сложное высказывание А

В - это высказывание, в котором утверждается одновременно наличие или отсутствие ситуаций А и В. В классической логике и на естественном языке эквиваленция выражается словосочетаниями: «Если и только если . . , то . .» , «В том и только в том случае, когда. . , то . .» «Тогда и только тогда, когда ..». "Тогда и только тогда когда, А необходимо и достаточно для В". В соответствии с определением эквиваленции как двойной импликации, ее можно представить как конъюкцию двух импликаций: из А следует В, а из В следует А

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

Например, А

В =

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

Как видим, все логические операции, за исключением операции отрицания, являются бинарными или двухместным» операциями, в которых обязательно присутствуют два операнда, а операция отрицания является унарной или одноместной логической операцией, которая действует на одно логическое высказывание или операнд.
2. Логические функции.

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

Логические функции от любого количества логических переменных часто называют двоичными функциями (Булевыми функциями), так как при любом допустимом наборе логических переменных логические функции принимают только два значения - истина или ложь (1 или 0). Каждая логическая переменная также может принимать только два значения - истина или ложь (1 или 0). Логические переменные иногда называют пропозиционными переменными {от propositio - предложение, высказывание).

Кроме высказываний и логических операций в алгебре высказываний рассматриваются логические константы. Таких логических констант две - 1 и 0. Они отождествляются с абсолютной истиной и абсолютной ложью.

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

Примерами составных высказываний могут быть следующие высказывания:

Приведенные выше высказывания называются формулами алгебры высказываний. Эти формулы состоят из простых высказываний А, В, знаков логических операций (

), а также скобок. Скобки, как и в обычной алгебре, указывают последовательность выполнения логических операций. При отсутствии скобок все логические операции выполняются в зависимости от их приоритетности. Иногда вместо приоритетности в алгебре логики говорят о "связывании" логических операций: первой всегда выполняется операция отрицания, затем конъюнкция

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