Лекции.Орг


Поиск:




Основные бинарные логические операции




 

Конъюнкцией называется бинарная логическая операция, соединяющая две двоичных переменных а и b, принадлежащих множеству {0,1}, в такую переключательную функцию с, которая равна 1 (истинна) только тогда, когда равны 1 (истинны) обе переменных. Операция конъюнкции обозначается символом Ù (&) или просто «×». В ряде случаев точку также опускают.

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

Таблица 14

Бинарная конъюнкция

b а 0 1  
0 0 0  
1 0 1 с=аÙb

 

Таким образом, конъюнкция – это операция В2aВ, где В – двухэлементное множество {0,1}, где 0,1 – значения истинности переменных. Известна также другая форма таблицы истинности – одномерная:

Таблица 15

Бинарная конъюнкция

а b с=аÙb
0 0 0
0 1 0
1 0 0
1 1 1

 

Конъюнкция n переменных истинна тогда и только тогда, когда все составляющие ее переменные истинны (равны 1).

Логическая операция, соответствующая союзу «или» в неразделительном смысле, называется дизъюнкцией (disjunctio – «разделение»). Пример дизъюнкции: «На экзамене по дискретной математике я получу 5 или 4».

Дизъюнкцией называется логическая операция, соединяющая две переменные а и b в такую переключательную функцию с, которая равна 0 (ложна) только тогда, когда ложны обе переменные (равны 0).

Дизъюнкция обозначается символом Ú.

В латыни союзу «или» в неразделительном смысле соответствует слово vel. Символ Ú происходит от первой буквы этого слова.

Таблица истинности дизъюнкции (одномерная) имеет вид табл. 16.

Таблица 16

Бинарная дизъюнкция

а b с=аÚb
0 0 0
0 1 1
1 0 1
1 1 1

 

Дизъюнкция n переменных ложна тогда и только тогда, когда все составляющие ее переменные ложны.

Логическая операция, соответствующая частице «не», словосочетанию «неверно, что», называется инверсией. Пример инверсии: «Студент Петров не отличник», «Неверно, что студент Иванов является спортсменом».

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

Инверсию а обозначают , используя знак дополнения множеств.

Таблица истинности унарной операции инверсии ВaВ имеет вид табл. 17.

Таблица 17

Бинарная инверсия

а
0 1
1 0

 

Логическая операция, соответствующая союзу «если...то», называется импликацией.

Примеры импликации: «Если вы будете хорошо заниматься в семестре, то сдадите экзамен по дискретной математике».

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

Импликация обозначается символом ®.

Таблица истинности импликации имеет вид табл. 18.

Таблица 18

Импликация

а b с=а®b
0 0 1
0 1 1
1 0 0
1 1 1

 

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

Логическая операция, соответствующая союзу «тогда и только тогда, когда», называется эквиваленцией(эквивалентностью).

Пример эквиваленции (эквивалентности): «Я поеду к морю тогда и только тогда, когда сдам экзамен по дискретной математике».

Эквиваленцией (эквивалентностью) называется логическая операция, соединяющая две переменных в такую ПФ, которая истинна тогда, когда обе образующих ее переменных одновременно истинны или одновременно ложны. Эквиваленция обозначается символом «.

Таблица истинности эквиваленции имеет вид табл. 19.

Таблица 19

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

а b с=а«b
0 0 1
0 1 0
1 0 0
1 1 1

 

Далее мы познакомимся с другими логическими операциями, которым нет простого эквивалента в разговорной речи, например, суммой по модулю 2 (исключающее ИЛИ).

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

Область определения ПФ n переменных – множество всех возможных наборов длины n при матричном задании ПФ, а при геометрическом способе задания – множество всех вершин n-мерного куба.

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

Например, для бинарной ПФ: вырожденная ПФ (табл. 20) – такая функция, которая зависит не от всех n переменных.

                                                                        Таблица 20

Вырожденная ПФ

 

BC

z

x3

х2

x1

0

0 0 0 1

0

0 1 1 1

0

1 0 2 1

0

1 1 3 1

1

0 0 4 0

1

0 1 5 0

1

1 0 6 0

1

1 1 7 0
           

 

Из таблицы (см. табл. 20) видно, что столбец функции является инверсным столбецу х3, т.е. , от х2, х3 – z не зависит!

Двоичные ПФ описывают элементную базу электронной вычислительной техники и устройств автоматики и телемеханики – комбинационные и последовательностные автоматы, которые будут рассмотрены в дальнейшем.

Итак, основные двоичные логические операции:

1) дизъюнкция Ú («ИЛИ»);

2) конъюнкция & («И»);

3) инверсия или отрицание («НЕ»);

4) импликация ® («ЕСЛИ, ТО»);

5) эквиваленция «(«ТОГДА И ТОЛЬКО ТОГДА, КОГДА»).

Кроме того, имеется операция:

6) сумма по модулю 2 Å («НЕВЕРНО, ЧТО ТОГДА И ТОЛЬКО ТОГДА, КОГДА» «ИЛИ-ИЛИ»).

Имеются также специальные операции:

7) стрелка Пирса ¯ («ИЛИ-НЕ»);

8) штрих Шеффера½(«И-НЕ») и др.

Алгебра, несущим множеством которой является множество ПФ, а операциями – дизъюнкция, конъюнкция и инверсия, называется булевой алгеброй ПФ.

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

,

означает, что бит a1 должен быть равен нулю и при этом биты a2 и a3 равны.

Решить логическое уравнение– значит, определить значения переменных, при которых соответствующая ПФ=1 (истинна), где 1 – константа.

Решить систему логических уравнений – значит определить значения переменных, при которых соответствующая ПФ=1.

Пример. Дана таблица истинности для трех ПФ (табл. 21).

Таблица 21

Таблица истинности трех ПФ

 

 

ВС

z1

z2

z3

a3 a2 a1
0 0 0 0 1 0 1
0 0 1 1 0 1 0
0 1 0 2 0 1 0
0 1 1 3 0 0 1
1 0 0 4 0 1 0
1 0 1 5 0 0 1
1 1 0 6 1 0 1
1 1 1 7 0 1 0

 

z1=0,6[1,2,3,4,5,7],

z2=1,2,4,7[0,3,5,6]=a1Åa2Åa3=1,

z3=0,3,5,6[1,2,4,7].

Здесь указаны номера наборов, на которых ПФ равны единице. Это так называемая символическая форма задания ПФ (СФ ПФ).

Видно, что общих решений нет.

Если же взять:

,

то получим:

z2=0,3,5,6[1,2,4,7], т.е.

решение системы z1,z2,z3=0,6.

Если же в уравнении указывается равенство с другой переменной или функцией, то, как мы уже знаем из теории множеств:

a1Åa2Åa3=a3, a1Åa2Åa3Åa3=0, a1Åa2=0.

Решение: 01,10 (a1a2).

 





Поделиться с друзьями:


Дата добавления: 2018-10-18; Мы поможем в написании ваших работ!; просмотров: 1166 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Два самых важных дня в твоей жизни: день, когда ты появился на свет, и день, когда понял, зачем. © Марк Твен
==> читать все изречения...

782 - | 716 -


© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.007 с.