Пять однобайтных кодировок кириллицыТема 5. Основы логики
Дидактические единицы: Логика как наука о правильных способах мышления; символическая логика. Семантика логических операторов. Доказательства логических равенств с помощью семантических таблиц, законы алгебры логики, правила преобразования логических выражений. Функционально полные языки логических операторов. Логические контуры, сводная таблица диаграмм Эйлера-Венна для бинарных функций F1-F16. Триггер - структурная единица (ячейка) памяти ЭВМ. Полусумматор двоичных чисел, сумматор на три входа (полный сумматор), шифратор. Аппаратная реализация логических контуров на базе МОП-транзисторов, вентиль "НЕ" (инвертор), вентиль "или-НЕ" ("стрелка Пирса").
Изучаемые вопросы
1. Понятие о логике как о науке. Практическое приложение логики.
2. Символическая логика. Семантика логических операторов.
2.1. Оператор инверсии (отрицания).
2.2. Оператор логического умножения (конъюнкция, логическое "И").
2.3. Оператор логического сложения (слабая дизъюнкция, логическое "ИЛИ").
2.4. Оператор импликации (условный оператор).
2.5. Сводная таблица бинарных логических операторов.
2.6. Логическое равенство (эквивалентность, равносильность).
2.7. Логическое неравенство (строгая дизъюнкция).
2.8. Штрих Шеффера (исключающее "ИЛИ", эксклюзия).
2.9. Стрелка Пирса.
2.10. Репликация.
2.11. Антиимпликация и антирепликация.
3. Доказательства логических равенств с помощью семантических таблиц.
4. Законы алгебры логики. Правила преобразования логических выражений.
5. Функционально полные языки логических операторов.
6. Логические контуры.
7. Сводная таблица диаграмм Эйлера-Венна для F1-F16
8. Триггер - структурная единица (ячейка) памяти ЭВМ.
9. Полусумматор двоичных чисел.
10. Сумматор на три входа (полный сумматор).
11. Шифратор.
12. Аппаратная реализация логических контуров на базе МОП-транзисторов.
12.1. Вентиль "НЕ" (инвертор)
12.2. Вентиль "или-НЕ" (стрелка Пирса").
Логика - наука (комплекс наук) о формах и способах правильного мышления. Под формой мышления понимают способ связи частей мыслимого целого (умозаключения, рассуждения, доказательства). Слово "логика" различные словари, научные или богословские, производят от древнегреческих слов
λογος - закон, порядок, слово, понятие, рассуждение, разум, сын Божий и др.
λογον διδοναι - давать отчёт.
В русском языке понятия "логика вещей" и "порядок вещей" - синонимы. Человек, владеющий логикой, может отличать правильные мысли (цепочки мыслей, рассуждения) от неправильных. Если вы правильно, логично рассуждаете, то производите на окружающих благоприятное впечатление. Если вы обнаружите ошибку в рассуждениях ваших собеседников, то сможете одержать верх в дискуссии, полемике, споре, и не дадите себя обмануть или убедить в чём-либо помимо вашей воли.
Оттачивая искусство одерживать верх в дискуссиях собеседников, в судебных тяжбах, логика за историю своего развития прошла несколько этапов: общая (традиционная, аристотелева), символическая (математическая) и т.д. Наиболее интересным и выгодным приложением достижений математической логики к практическим нуждам людей стало создание счётно-решающих устройств, электронных вычислительных машин. Человек сумел познать наиболее общие, присущие всем людям законы мышления и смоделировать работу своего мозга, "вручив" частично функции вычислений и умозаключений сложным техническим неживым устройствам.
Тема "Основы логики" в курсе информатики как раз и позволяет узнать, каким способом электронное счётное устройство может помочь человеку решать стоящие перед ним задачи почти так же, как их решает сам человек, но в тысячи тысяч раз быстрее, чем человек успевает их решать.
 |
Логика должна была начаться с осознания человеком того, что есть внешний мир и есть его видимость, образ мира в голове человека. Видим ли мы то, что есть на самом деле? Ответ на этот вопрос довольно сложен, и от того, кaк человек на него отвечает, зависит то, к какой теории познания он обращается, если даже сам человек не ведает ни о каких теориях познания. Если мы скажем, что "то, что мы видим, ощущаем, и есть внешний мир", что "внешний мир именно такой, каким мы его воспринимаем", то из этого следует, что Земля плоская, а Солнце вращается вокруг неё. В самом деле, фотография Земли из космоса свидетельствует, что земной диск плоский. Тогда земной глобус станет моделью плоской Земли, картой земного диска, для удобства обозрения спроецированной на сферу с подставкой. Кроме того, микробов и вирусов, молекул и атомов, подлости и совести нет, так как их не видно. И такие нелепые выводы следуют из первоначального решения о том, что реальный мир и его образ одно и то же. |
Представим, что четыре радиолокационные станции обнаружили в небе над страной, которую они прикрывают, самолёт-шпион. Пусть каждая РЛС сообщила своим управляющим структурам об этом самолёте. Если каждая управляющая структура сообщит главнокомандующему страны о замеченном самолёте, то президент получит четыре разных сообщения из четырёх разных источников. Значит ли это, что и самолётов обнаружено четыре? Если да, то мы всё ещё заблуждаемся, что "сам мир и его образ в нашей голове - одно и то же". Более достоверным же будет ответ, что сам внешний мир (источник образа) и образ мира, отражение мира в головах людей различные вещи. Приведём сравнительную таблицу внизу:
|
|
|
| Попадание в глаза фотонов с длиной волны 4·10 -5 см |
Красный цвет |
| Интенсивное движение молекул воды в парилке бани |
Тепло |
| Прикосновение раскалённого стального прута к коже |
Боль |
| Продольные колебания воздуха со скоростью 330 м/с, воспринимаемые ухом |
Звук |
Из таблицы можно заключить, что причиной наших ощущений становятся физические явления, феномены, некие движущиеся сущности. Известно, что инородное тело, продвигаясь в тканях организма, вызывает болевые ощущения, но после того, как оно прекращает движение относительно тканей, ощущение боли прекращается. Кроме того, физические тела разной формы и состава, проникая в организм и продвигаясь внутри, вызывают совершенно одинаковые болевые ощущения. Это позволяет заключить, что наши ощущения и то, что их вызывает - не одно и то же.
Древние римляне пользовались словом "estina", обозначая им действительное положение вещей, то, что есть на самом деле. В русском языке для этого пользуются словом "истина".
Есть правильные мысли. Они истинны, т.е. соответствуют действительности, своим объектам.
Есть ложные мысли, они сознательно (умышленно) искажают действительность.
Ещё есть заблуждения - неумышленное искажение действительных связей между объектом и мыслью об объекте. Все мысли, выраженные с помощью языка, называются высказываниями.
Высказывание (суждение) - это изречённая мысль, которая является ответом на вопрос о степени неопределённости наших знаний предмета вопроса. Мысль всегда изрекается о чём-то или о ком-то. Когда мысль изрекается о самой себе, она становится парадоксальной.
Высказывание уменьшает степень неопределённости наших знаний о предмете мысли (об объекте) в два раза. В курсе информатики изучаются начала двузначной символической логики. В такой логике высказывание имеет только два логических значения - оно может быть либо истинным, либо ложным, но не то и другое вместе. Значит, любое высказывание несёт хотя бы 1 бит информации в своём логическом значении. Вследствие этого в формальной (двузначной) логике заблуждение будет считаться ложью.
Кроме того, высказывание в символической логике считается пропозициональной переменной (proposition - англ. высказывание), так как всегда оказывается либо истинным, либо ложным. Субъектно-предикатная структура суждений (высказываний) в логике высказываний не принимается во внимание, т.е. высказывание считается чем-то неделимым, целым, не имеющим внутри себя частей, своего рода логическим "атомом".
Не все выражения естественных языков являются высказываниями:
|
| |
| Высказывание (суждение) |
Не высказывание (не суждение) |
| 1. Простое повествовательное предложение (далее - ППП): "Сейчас зима"; "Розы - красные". |
1. ППП, высказывающееся о самом себе: "Это суждение ложно" |
| 2. Риторический вопрос: суждение выражается в грамматической форме вопроса, ответ на который подразумевается заранее известным: "Ребята! Не Москва ль за нами?" |
2. Любой вопрос, исключая риторический: "Как пройти в библиотеку?" |
| 3. Восклицательное предложение: "Как хороши, как свежи были розы!" |
3. Побудительное предложение (приказ, императив): "Пшёл вон!" "Говори кратко. Проси мало. Уходи быстро." (Пётр I). |
В учебниках информатики логические величины определяются несколько иначе (более формально):
Логическое выражение (ЛВ) - это высказывание, по поводу которого можно заключить, истинно оно или ложно. ЛВ, подобно математическому выражению, вычисляется (выполняется), но в результате получается не число (сумма, разность и др.), а логическое значение - истина (true) или ложь (false). ЛВ - всегда ответ на вопрос: "Истинно ли данное высказывание?".
Код логической величины true=1, а логической величины false=0, поэтому для логических величин истинно неравенство true>false (1>0). Кроме того, в качестве логических выражений используются логические смысловые связки "не", "и", "или", "если..., то..." и некоторые другие. Это служебные слова, которые выполняют роль знаков логических операций, операторов.
На самом же деле, как будет показано в дальнейшем, состояния пропозициональных переменных (Истина, либо Ложь) и сами пропозициональные переменные (высказывания, операнды) суть разновидности логических операторов. Для нас пока важно различение:
- "логическое значение пропозициональной переменной" (её состояние - Истинность или Ложность, логическая 1 или логический 0);
- "логическая переменная" (операнд, то с чем работает оператор);
- "логический оператор" (то, что обрабатывает операнды).
| Имя оператора | По-русски | In English | Начертание |
| 1.Отрицание (инверсия) |
НЕ |
NOT |
¬a (a∧b) |
| 2.Конъюнкция (логическое умножение) |
И |
AND |
a∧b a•b a&b |
| 3.Слабая дизъюнкция (логическое сложение) |
ИЛИ |
OR |
a∨b |
| 4.Импликация (условный оператор) |
ЕСЛИ..., ТО... |
IF...THEN... |
a→b a⊃b |
| 5. Логическое равенство (эквиваленция) |
равно, эквивалентно |
equal to |
a≡b |
Выражения, содержащие логические операции булевой алгебры , называются сложными логическими выражениями. Отрицание - одноместная (унарная, от лат. unarius - единичный) операция, применяется к одной логической величине (к одному логическому операнду). Все иные (логические сложение, умножение) двух- и более местные, они связывают между собой минимум две логические величины (два операнда), исключая отрицание. Их называют бинарными (binarius - лат. двойной), тернарными (ternarius - лат. тройной), тетрарными (tetrarius - лат. четверичный) и т.п.
В сложном логическом выражении операции выполняются по приоритетам. Если порядок операций надо изменить - применяют круглые скобки. При наличии скобок действия над логическими величинами выполняются по приоритету сначала в скобках, затем по приоритету вне скобок. Изучим логические операторы по приведённому порядку.
2.1. Оператор инверсии (отрицания).
Что делает этот оператор? Он изменяет значение логической переменной на противоположное: истину на ложь, а ложь - на истину.
В русском языке выражается с помощью частицы "не", "нет"; предлога "без"; приставок "без-", "бес"; союза "неверно, что..."; в словах иностранного происхождения приставками "а-" и "анти-".
Для выяснения семантики логических операторов (значений, которые им придаются, приписываются) люди придумали семантические таблицы. В них слева записываются логические переменные, участвующие в логическом выражении, а справа от них - пошагово части формулы в порядке приоритета операций.
Для инверсии (отрицания) семантическая таблица строится так:
| Входной столбец | Выходные столбцы | Входной столбец | Выходные столбцы | ||||||
| a | ¬a | ¬¬a | ¬¬¬a | a | ¬a | ¬¬a | ¬¬¬a | ||
| И | Л | И | Л | 0 | 1 | 0 | 1 | ||
| Л | И | Л | И | 1 | 0 | 1 | 0 | ||
| I | II | III | IV | I | II | III | IV | ||
Поскольку инверсия - унарный оператор, во входной столбец вносится переменная а (операнд), под неё - возможные состояния (логические константы истина и ложь). В выходном столбце (выходных столбцах) вписывается операнд с оператором (операторами), а под ним - получаемые в результате действия оператора логические значения. Если отрицаний несколько, справа от входного столбца приписывается столько выходных столбцов, сколько операторов инверсии есть в высказывании.
Очевидно, что столбцы I и III совпадают между собой по логическим значениям, как совпадают между собой столбцы II и IV. Теперь можно сформулировать правило вычёркивания: если в логическом выражении встречается несколько отрицаний подряд и между ними нет скобок, то их можно попарно вычёркивать.
В русском языке правило вычёркивания можно применять к предложениям: ведь сказать "Он держал себя не без достоинства" то же самое, что сказать "Он держался достойно". В содержательном плане инверсии соответствует вывернутая рубашка, обманутый обманщик. Так, на карнавале можно делать всё, что нельзя в будние дни.
Следует помнить, что в логике высказываний субъектно-предикатная структура суждений игнорируется, и отрицание должно применяться ко всему высказыванию, а не к его частям. Если неверно (ложно) утверждение "Верно, что все розы красные", то истинно (верно) только утверждение "НЕверно, что все розы красные". Утверждение "Все розы НЕ красные" также будет ложно, поскольку в таком высказывании отрицается лишь предикат суждения, а должно инвертироваться всё высказывание как единое целое.
В описании работы технических устройств (аппаратной реализации логических контуров) семантические таблицы заполняются по правилам, описанным выше, за одним исключением: заполнение логических значений переменной идёт сверху вниз от логических нолей к логическим единицам. Следовательно, матрица семантической таблицы инверсии будет выглядеть иначе (сравните левую и правую стороны таблицы). Оба способа записи (И/Л-таблица и 1/O-таблица) идентичны друг другу, но матрица логических значений одного "опрокинута" для другого.
Иногда для записи и выявления отношений объёмов классов предметов, о которых произносятся высказывания, используются диаграммы Эйлера - Венна, т.е. к логике высказываний применим математический аппарат логики классов. Переменная а обозначается кругом внутри прямоугольника, называемого "универсумом рассуждения". Область внутри прямоугольника за пределами круга является дополнением к классу a и обозначается как ¬a.
Пусть переменная а - класс "зелёные яблоки". Тогда дополнением к нему будет ¬a ("НЕзелёные яблоки"). Вместе класс а и дополнение к нему ¬a
исчерпывают родовое понятие (класс, множество) "яблоки", т.е. а + ¬a ≡
1. Или, что то же самое, но более привычно:
Введём правила для закраски областей универсума рассуждения. Будем заливать цветом только ту область, которая соответствует логической единице (истине) в выходном столбце. Высказывание ¬a истинно тогда и только тогда, когда операнд a ложен. Следовательно, внутри круга a краски быть не должно, а за его границами внутри универсума рассуждения должен быть цвет.
Инвертор. При разработке логических схем компьютера для обозначения устройства, работа которого описывается таблицей инверсии, используется этот значок. Входы в устройство традиционной рисуются слева, выходы - справа.
Если на вход а слева поступает импульс 1, то на выходе (справа) будет получен сигнал 0. И наоборот, если на вход а поступит сигнал 0, на выходе инвертор выдаст сигнал 1. Таблица возможных состояний инвертора на входе и выходе приведена справа.
Что делает: бинарный оператор соединяет между собой два класса предметов, и от этого соединения образуется новый (третий) класс-потомок, совмещающий в себе признаки исходных классов-предков. Он отображает соединение, единство, связь двух (или более) вещей в действительности или в наших мыслях о действительности.
В русском языке выражается союзами "... и ..."; "..., но ..."; "..., а ..."; "..., да и ..."; "..., а и ..."; "..., но и ..."; "не только..., но и ..."; "..., хотя ..."; "..., который…"; "..., зато ..."; "..., однако ..."; "как ..., так и ...". Знаки препинания, такие, как запятые, точки с запятой, тире, точки в конце предложений конъюнктивно (от лат. conjunctio - я соединяю) соединяют их в связный текст. Т.е. можно считать, что предложения текста логически умножаются друг на друга.
Составим семантическую таблицу для логического умножения. Пусть а = "Жених явился"; b = "Невеста явилась"; a&b ≡ a∧b ≡ "Брак возможен". Заполнение семантической таблицы для конъюнкции по сравнению с оператором инверсии будет более сложным. В операции участвуют два операнда, у каждого может быть два состояния, стало быть, надо рассмотреть все их возможные сочетания по истине и лжи. Если заменить логические значения наличием или отсутствием фигурок жениха или невесты в соответствующих столбцах, получим идентичные по смыслу табличные записи. В отечественной традиции логическое умножение пишется заглавной греческой "лямбдой" (Λ), применим эту запись к И/Л-таблице. В учебной литературе конъюнкция чаще обозначается амперсендом (&), применим такую запись к 1/O-таблице.
|
|
|
|
а |
b |
a∧b |
|
|
а |
b |
a&b |
|
|
|
|
|
|
|
И |
И |
И |
|
|
0 |
0 |
0 |
|
|
Брак невозможен |
|
|
|
Брак невозможен |
И |
Л |
Л |
|
|
0 |
1 |
0 |
|
|
Брак невозможен |
|
|
|
Брак невозможен |
Л |
И |
Л |
|
|
1 |
0 |
0 |
|
|
Брак невозможен |
|
|
|
Брак невозможен |
Л |
Л |
Л |
|
|
1 |
1 |
0 |
|
|
|
Теперь наглядно представлено "опрокидывание" матрицы И/Л-таблицы в 1/O-таблицу (или, если угодно, наоборот, 1/O-таблицы в И/Л-таблицу). Очевидно, что выбираемый способ записи зависит от предпочтений человека и не меняет смысла употребляемого оператора.
Примеров соединений разных вещей можно привести достаточно много. Если поместить натрий в раствор соляной кислоты, начнётся их соединение, причём из раствора выделится водород H2↑, а в жидкости останется соль NaCl↓. Ясно, что газ и соль непохожи на исходные металл и раствор кислоты по свойствам и внешнему виду.
Если на белый экран навести лучи от жёлтого и синего прожекторов и пересечь часть их площадей, то место пересечения кругов будет выглядеть зелёным. Зелёного цвета не было до начала взаимодействия жёлтого и синего кругов. Очевидно, что в месте пересечения сочетаются разные длины волн электромагнитного излучения и в глазу возникает ощущение цвета иного, чем прежде.
Если представить, что левый круг - множество отличников, а правый - спортсменов, то "чечевицу" пересечения должно назвать "спортсмены И отличники". Полученный в результате умножения новый класс вещей по объёму (площади) чаще всего меньше исходных (классов-прародителей). Так, точно неизвестно, больше или меньше два множества "кислые яблоки" и "сладкие яблоки" по объёму в целом, нежели множество "кисло-сладкие яблоки".
В алгебре высказываний правило для логического умножения таково: логическое умножение истинно, только если все операнды, участвующие в нём, истинны. Оператор логического умножения может быть бинарным (a&b), тернарным (a&b&c), тетрарным (a&b&c&d) и т.д. При любом числе входящих операндов выходной столбец семантической таблицы будет истинным только в одном случае. На схеме вверху изображена диаграмма Эйлера - Венна для тернарного оператора логического умножения. Класс вещей, обладающий всеми признаками трёх исходных классов-прародителей, находится в самом центре, в белом выпуклом треугольнике, там, где a&b&c≡И.
 |
 |
Диаграмма Эйлера - Венна для бинарного оператора логического умножения расположена справа от семантических таблиц. Правила закраски областей, описаны в 2.1. Согласно им, цветом залита только область пересечения множеств a&b. Оставшиеся полумесяцы a и b, а также область дополнения к классу не заливаются.
В теории множеств операции логического умножения соответствует пересечение классов.
Логическое умножение можно смоделировать с помощью релейно-контактной схемы - пары ключей a и b, соединённых последовательно. Электроток через такое соединение пойдёт, только если замкнуты оба ключа. Рассмотрите соответствие семантической И/Л-таблицы релейно-контактной схеме:
|
а |
b |
a∧b |
Релейно-контактные схемы |
|
И |
И |
И |
|
|
И |
Л |
Л |
|
|
Л |
И |
Л |
|
|
Л |
Л |
Л |
|
Конъюнктор. При разработке логических схем компьютера для обозначения устройства, работа которого описывается таблицей логического умножения, используется этот значок вверху. На вход a конъюнктора последовательно поступают импульсы 0,0,1,1 (как в первом входном столбце), а на вход b - импульсы 0,1,0,1 (как во втором входном столбце). Внутри устройства сигналы логически перемножаются, и на выходе справа получается последовательность 0,0,0,1 (как в выходном столбце семантической таблицы).
Что делает: бинарный оператор логического сложения разъединяет между собой два класса предметов, но не полностью, не до конца. Он выражает собой выбор из нескольких возможностей по принципу "или то, или другое, или то и другое вместе". Оператор "логическое сложение" допускает совместимость операндов, и его называют «неисключающее "ИЛИ"».
В русском языке выражается союзами "... или ...", "либо ..., либо ...", "или ..., или оба", "... или если оба".
Построим семантическую таблицу операндов, соединённых слабой дизъюнкцией (disjunctio - лат. я разобщаю, обособляю, разъединяю). Пусть
a = "Кролик даст Винни Пуху мёда";
b = "Кролик даст Винни Пуху сгущенного молока";
aVb = "Винни Пух не голоден"
Вспомним известный диалог Винни Пуха и Кролика из отечественного мультфильма "Винни Пух идёт в гости" режиссёра Ф.Хитрука:
 |
|
 |
Если неверны оба высказывания (a и b, по первой строке семантической таблицы), то ложно их логическое сложение aVb, т.е. неверно, что "Винни Пух не голоден". Если хотя бы один из операндов (a либо b) истинный, то верно, что "Винни Пух не голоден". aVb истинно и в том случае, если оба операнда истинны (4-я строка семантической таблицы). Вероятно, Кролик хотел сэкономить на угощении и предложил гостю выбор, а Винни Пух знал логику высказываний и сумел обратить вопрос Кролика себе на пользу.
 |
Человечество подразделяется на 4 типа по группам крови в полном соответствии с семантической таблицей логического сложения. Может быть, это является одним из прямых доказательств того, что логика идей определяется логикой (порядком) вещей. Медики выделяют по системе AB0 4 группы крови, обозначаемые буквенными и цифровыми символами. Отсутствие обоих антигенов или антител обозначают цифрой 0. I группа крови содержит только антитела a, b и обозначается 0ab; II группа крови содержит антиген А и антитело b, обозначается Аb; III группа крови содержит антиген В и антитело a, обозначается Вa; IV группа крови содержит только антигены А и В, обозначается АВ0. Можно построить расширенную семантическую таблицу, в которой определим антитело как антипод (отрицание) антигена (A≡¬a, B≡¬b), а пустые клетки обозначают отсутствие того или иного фактора. |
 |
 |
Очевидно, что столбцы "Антигены" полностью повторяют входные столбцы И/Л-таблицы логического сложения, а столбцы "Антитела" - входные столбцы 1/0-таблицы логического сложения. Антигены крови человека взаимно обратны антителам, И/Л-таблица взаимно обратна 1/0-таблице. |
 |
В алгебре высказываний правило для логического сложения формулируется так: оператор логического сложения будет истинным, если хотя бы один из операндов, участвующих в нём, истинный.
В теории множеств операции логического сложения соответствует объединение множеств. Если левый круг - множество отличников, правый - множество спортсменов, область их пересечения - множество"спортсмены И отличники", то в множество "спортсмены ИЛИ отличники" войдут все три закрашенных области.
Самостоятельное сравнение диаграмм Эйлера - Венна для логического сложения и логического умножения, раскрашенных по правилам в 2.1., позволит понять, почему объём множества "красные И зелёные яблоки" меньше объёма множества "красные ИЛИ зелёные яблоки".
|
Логическое умножение |
Логическое сложение |
 |
 |
Логическое сложение можно смоделировать с помощью релейно-контактной схемы - пары ключей a и b, соединённых параллельно. Электроток через такое соединение пойдёт, если замкнут хотя бы один из ключей. Рассмотрите соответствие семантической И/Л-таблицы релейно-контактной схеме ниже:
|
а |
b |
aVb |
Релейно-контактные схемы |
|
И |
И |
И |
|
|
И |
Л |
И |
|
|
Л |
И |
И |
|
|
Л |
Л |
Л |
|
Дизъюнктор. При разработке логических схем компьютера для обозначения устройства, работа которого описывается таблицей логического умножения, используется этот значок слева от семантической таблицы. На вход а дизъюнктора последовательно поступают импульсы 0,0,1,1 (как в первом входном столбце), а на вход b - импульсы 0,1,0,1 (как во втором входном столбце). Внутри устройства сигналы логически складываются, и на выходе справа получается последовательность 0,1,1,1 (как в выходном столбце семантической таблицы).
Что делает: бинарный оператор импликации соединяет между собой два высказывания (явления) как причину и следствие, выражает связь между достаточным условием и его последствием. Наличие события, о котором говорится в а, является достаточным основанием для того, чтобы имело место событие, указанное или мыслимое в b. Операнд а в такой операции называется антецедентом (от лат. antecedent - предшествующий), операнд b - консеквентом (от лат. consequens - последующий).
В логике высказываний антецедент есть только достаточное условие истинности консеквента, консеквент есть только необходимое условие истинности антецедента. Из-за такой асимметрии перестановка местами операндов импликации в общем случае неправомерна. Сравните два высказывания: "Если пойдёт дождь, то я раскрою зонт" и "Если я раскрою зонт, то пойдёт дождь".
В русском языке выражается союзами "если…, то...", "всегда, если …, то …", "a включает b", "если …, тогда …", "a есть достаточное условие для b", "когда…, тогда…", "при наличии А всегда имеет место В", "А влечёт В", "А, значит, В", "из А следует В" и т.д.
Составим семантическую таблицу импликации (от лат. implicite
- тесно связываю). Пусть
а = "Зерно посадили в тёплую влажную почву";
b = "Зерно проросло";
а
⊃ b = "Если зерно посадить в тёплую влажную почву, то оно прорастёт".
|
а |
b |
a⊃b |
Комментарии к семантической таблице |
|
И |
И |
И |
Первая строка. Допустим, что зерно посадили в тёплую влажную почву и оно проросло. Так люди практиковали по весне миллионы раз, и в подавляющем большинстве случаев посеянные зёрна прорастали. Операция посева семян стала восприниматься как причина прорастания зерна. В рассмотренном случае условный оператор считается истинным. |
|
И |
Л |
Л |
Вторая строка. Одно из зёрен посадили в тёплую влажную почву в массе других, а именно оно не проросло (утратило всхожесть). Ясно, что причинно-следственная связь ("посадил⊃обязательно взошло") в данном случае не срабатывает. И это связано с течением объективных процессов в мире, внешнем для нашей головы. Ведь сами процессы протекают независимо от наших мыслей о них! В этом случае условный оператор считается ложным. |
|
Л |
И |
И |
Третья строка. Зерно не садили в тёплую влажную почву, а залили водой в стеклянной банке и выставили на подоконник дома на кухне. Зерно проросло. Здесь особенно чётко видно, что достаточное условие необязательно есть необходимое условие. Вместе с тем определяющим, главным будет результат - прорастание зерна. В этом случае условный оператор считается истинным. |
|
Л |
Л |
И |
Четвёртая строка. Зерно никуда не помещали, оно лежит как стратегический запас, как страховка на будущую весну на случай заморозков, уничтожающих посевы. Зерно не прорастает потому, что не созданы достаточные условия для его проращивания. (Аргумент для лентяев: "Если бы мы отсеялись, зерно проросло бы"). Нет следствия потому, что не было причины. И в этом случае условный оператор считается истинным. |
В алгебре высказываний правило для импликации формулируется так: условный оператор будет ложным, только если антецедент истинный, а консеквент ложный, или иначе - когда есть причина, а следствия нет.
Примеры импликативных высказываний в русском языке: "Лекция кончилась, и студенты разошлись", "Если я буду молчать, я никогда не начну", "Мне это не нравится, значит, это никуда не годится", "Щёлкни кобылу в нос - она махнёт хвостом", "Всегда, когда я хочу тебя навестить, тебя нет дома".
Построим для импликации диаграмму Эйлера-Венна по принятым правилам:
|
Семантическая таблица |
Диаграмма Эйлера - Венна |
|
|
|
Каждая пропозициональная переменная в двузначной логике либо истинна, либо ложна, но не то и другое вместе. Число сочетаний двух таких пропозициональных переменных будет 22•2= 16, т.е. два высказывания можно связать шестнадцатью разными способами.
Введём правила построения сводной И/Л-таблицы. В первой строке запишем восемь раз "Истина" и восемь раз "Ложь". Во второй строке четыре раза "Истина" и четыре раза "Ложь" дважды. В третьей строке - дважды "Истина" и дважды "Ложь" четыре раза. В четвёртой строке - "Истина", затем "Ложь" восемь раз подряд.
Для построения сводной 0/1-таблицы первую строку надо заполнить восемь раз нолями и восемь раз единицами. Во второй строке - дважды по четыре ноля и по четыре единицы. В третью строку внесём четырежды два ноля и две единицы. В четвёртой строке попеременно восемь раз 0 и 1. Следует добавить к этой таблице строку с номерами логических функций от F1 до F16 включительно.
Функции F4 и F13, F6 и F11 являются переменными А, В и их отрицаниями. Функции F1 и F16 являются логическими константами: F1 есть выходной столбец тождественно-ложных формул (противоречий), F16 - выходной столбец для тождественно-истинных формул (законов, или тавтологий).
Что делает: бинарный оператор логического равенства считается истинным, если два составляющие его операнда совпадают по своим логическим либо оба вместе истинны, либо оба вместе ложны. Эквивалентная связь двух явлений такова, что существование первого обусловлено существованием второго, и наоборот. Например, дедушкой или бабушкой можно быть только при наличии хотя бы одного внука (одной внучки). Пока нет внуков, человек не может считаться дедушкой (бабушкой).
В русском языке выражается союзами "тогда и только тогда, когда…", "точно тогда, когда", "… если и только если …", "если…, то… и обратно", "для того, чтобы …, необходимо и достаточно …", "эквивалентно" (от лат. aequivalens - равносильный, равноценный, равнозначный).
Например, российский гражданин становится совершеннолетним тогда и только тогда, когда он достиг 18 лет.
| Эквиваленция в диаграммах Эйлера - Венна выглядит так: | |
| Семантическая таблица для равносильности | Диаграмма Эйлера - Венна для логического равенства |
 |
 |
Оператор равносильности используется при замене одних логических операторов и формул другими.
Порядок формальных доказательств с помощью семантических таблиц:
- Расставить номера операторов в порядке приоритета слева, а затем справа от логического равенства. Оно выполнится в последнюю очередь.
- Определить количество участвующих операндов n и заполнить входные столбцы константами "Истина" и "Ложь" по формуле 2n=N. По ней в семантической таблице из двух операндов нужны четыре строки, для трёх - восемь и т.д.
- Выполнить операторы согласно расставленным номерам.
К примеру, требуется доказать, что 1) a⊃b≡¬aVb; 2) ¬(aVb)≡¬a&¬b
Что делает: бинарный оператор строгой дизъюнкции выражает тот факт, что одна из имеющихся возможностей исключает все остальные. Это альтернатива либо того, либо другого варианта развития событий. Строго-разделительная дизъюнкция означает такую связь двух операндов, при которой наличие одного из дизъюнктов полностью исключает всё то, что может принадлежать (мыслиться) другому дизъюнкту.
В русском языке выражается союзами "либо…, либо…", "или…, или…", выражениями "желательно…, но невозможно", "либо так, либо никак".
Примеры: "Электрический ток бывает или постоянный, или переменный". "Хоть видит око, да зуб неймёт". "Этот человек зряч или слеп".
Правило для строгой дизъюнкции: она истинна, когда истинен только один из операндов, в ней участвующий.
|
Возможные диаграммы Эйлера - Венна для логического неравенства и семантические таблицы | ||
|
|
|
|
Можно выразить строгую дизъюнкцию с помощью релейно-контактных схем: понадобятся две пары ключей, соединённых параллельно. Добавим в семантическую таблицу рядом со входными столбцы ¬a и ¬b. Это не изменит результата операции, но свяжет таблицу со схемами. Исследование таблицы показывает нам, что ключи связаны попарно таким способом: если ключ a (b) открыт, то его антипод ¬a (¬b) закрыт, и наоборот.
Эта релейно-контактная схема будет работать таким порядком
 |
Для первой строки расширенной семантической таблицы Ключи ¬a и ¬b разомкнуты, и ток по цепи пройти не может |
Для второй строки расширенной семантической таблицы Ток по цепи пройдёт по ключам ¬b и а. | |
Для третьей строки расширенной семантической таблицы Ток по цепи пройдёт по ключам ¬a и b. | |
Для четвёртой строки расширенной семантической таблицы Ключи a и b разомкнуты, ток по цепи не пойдёт. |
Что делает: бинарный оператор исключающего "ИЛИ" выражает тот факт, что одно высказывание исключает другое, что a и b несовместимы по истинности. Эксклюзия в принципе допускает, что a и b могут быть ложными вместе.
В русском языке выражается союзами "то ли …, то ли ...". Человек мог родиться или в Перми, или в Кунгуре (ясно, что в двух местах сразу родиться невозможно, но можно родиться в каком-либо третьем). "Первый урок сегодня будет или физикой, или физкультурой" (а может быть, и каким-то другим).
|
|
|
По своему содержанию штрих Шеффера является антиконъюнкцией, отрицанием логического умножения. Тогда будут равносильными формулы: a|b≡(a&b). Доказательство с помощью семантической таблицы предлагается провести самостоятельно.
|
Логический контур "и-НЕ". При разработке логических схем компьютера для обозначения устройства, работа которого описывается таблицей штриха Шеффера, используются значки слева или справа. Рассмотрим правый логический контур. На вход а контура "и-НЕ" последовательно поступают импульсы 0,0,1,1 (как в первом входном столбце), а на вход b - импульсы 0,1,0,1 (как во втором входном столбце). Внутри конъюнктора сигналы логически умножаются, затем сигнал с выхода конъюнктора попадает в инвертор, и на выходе справа получается последовательность 1,1,1,0 (как в выходном столбце семантической таблицы). |
|
Что делает: бинарный оператор "стрелка Пирса" соединяет между собой два операнда так, что оператор будет истинным тогда и только тогда, когда ложны составляющие его операнды.
В русском языке выражается союзами "ни ... ни ...". В английском - конструкцией "neither ... nor...".
Оператор a↓b читается "ни a, ни b". Впервые исследован и введён в науку Чарльзом Пирсом в конце XIX в. Примеры: "Ни рыба ни мясо". "Стоял в поле теремок ни низок ни высок". "Не в силах я жить ни с тобой, ни в разлуке с тобой" (Овидий). "Когда человек не хочет знать правды, то ни доводы разума, ни добрые советы не помогут".
По содержанию стрелка Пирса является антиподом логического сложения, отрицанием слабой дизъюнкции. Тогда будут равносильны формулы: a↓b≡(a V b). Доказательство с помощью семантической таблицы предлагается провести самостоятельно.
|
|
 |
Логический контур "или-НЕ". При разработке логических схем компьютера для обозначения устройства, работа которого описывается таблицей стрелки Пирса, используются значки слева или справа. Рассмотрим правый логический контур. На вход а контура "или-НЕ" последовательно поступают импульсы 0,0,1,1 (как в первом входном столбце), а на вход b - импульсы 0,1,0,1 (как во втором входном столбце). Внутри дизъюнктора сигналы логически умножаются, затем сигнал с выхода дизъюнктора попадает в инвертор, и на выходе справа получается последовательность 1,0,0,0 (как в выходном столбце семантической таблицы). |
 |
Что делает: бинарный оператор репликации соединяет между собой два операнда (антецедент и консеквент) как необходимое условие и его следствие. Позволяет умозаключать от следствия к причине.
В русском языке выражается союзами "только если ..., то ...", высказыванием "А реплицирует В".
Поскольку a⊂b≡b⊃a, то репликацию иногда называют обратной импликацией. Примеры репликативной связи высказываний: "Если человек тратил деньги, то он их имел"; "Только если замкнут контакт, лампочка горит"; "Люди перестают мыслить, когда перестают читать"; "Я растратил душу по кусочкам, а она была, была, была!.."
В реальной жизни достаточно часто приходится умозаключать от консеквента: если человек оставил отпечатки пальцев на месте преступления (b), значит, он там был (a). Противоречит такому умозаключению следующее: человек не был на месте преступления (a), а его отпечатки пальцев есть (b). Такая ситуация отображена в третьей строке семантической И/Л-таблицы (во второй строке 0/1-таблицы).
 |
|
Операторы под именами F3 и F5 сводной 1/0-таблицы бинарных логических операторов характеризуют антиимпликацию и антирепликацию. Антирепликация обозначается как , читается "не А, а В". Например, "Классик не подлежит критике, но подлежит исследованию" (М. Шагинян). "Не транжирить национальное богатство, не вывозить за рубеж, а приумножать его внтури России".
Антиимпликация обозначается как и читается как "А, но не В". Антиимпликация и антирепликация суть отрицания импликации и репликации, что вытекает из сопоставления их возможных представлений:
Результат табличных вычислений может совпадать с F1 сводной 1/0-таблицы бинарных логических операторов, в этом случае формула будет тождественно-ложной (невыполнимой), логическим противоречием. Все остальные формулы считаются выполнимыми. Если результат вычислений совпадает с F16 той же таблицы, то перед нами тождественно-истинное выражение, логический закон, выполнимый при любых значениях входящих в него переменных. Функции F2-F15 считаются нейтральными выражениями, они выполнимы при одних значениях входных величин и невыполнимы для других. Чаще всего требуется вычислить выходное значение семантической таблицы логического выражения или доказать равносильность двух сложных логических выражений.
Докажем, что выражение a&¬a≡Л (тождественно-ложно), и что выражение aV¬a≡И (тождественно-истинно).
Докажем, что равносильны выражения a⊃¬b и (a&b) для случаев И/Л- и 0/1-таблиц.
Для каждого выражения составлены отдельные семантические таблицы. Столбцы 1 и 2 нет нужды переписывать несколько раз, поэтому таблицы можно совместить, сделав общими начала. Для столбца 3 применены значения операторов отрицания и логического умножения по определению. Для столбца 4 применено правило для импликации (она ложна, только если антецедент истинный, а консеквент ложный) и правило для отрицания (инвертируется то, что в скобке (a&b)). Сократим записи доказательств, удалив повторяющиеся столбцы и оставив нумерацию так, как было выше. Ниже будем сокращать записи по такому же принципу.
Установим табличным способом, являются ли формулы a⊃(b⊃c) и a&b⊃c равносильными. Для трёх операндов понадобится семантическая таблица из восьми строк. Операции выполним в порядке приоритета.
Табличный метод доказательства тождества формул является самым надёжным. Но если число операндов более 4-х, становится затруднительным выписывать и сопоставлять столь длинные (32 строки, 64 строки и т.д.) столбцы. Для формализации вычислений вводятся правила операций с операндами, позволяющие сводить сложные высказывания к относительно простым. Таблица функций F1-F16 позволяет заменять одни операции на другие, как это делалось выше. Такие операции проводятся на основе законов алгебры логики.
4.1. Закон двойного отрицания: ¬¬a ≡a (здесь применяется правило вычёркивания).
4.2. Закон коммутативности выражается в том, что результат операции с двумя элементами не зависит от порядка, в каком берутся эти элементы. В общем случае бинарная операция a*b называется коммутативной, если a*b=b*a. (* - любой возможный логический оператор):
Коммутативны шесть логических операций:
| a&b≡b&a | aVb≡bVa | aVb≡bVa | a|b≡b|a | a↔b≡b↔a | a↓b≡b↓a |
4.3. Закон ассоциативности (сочетательный закон) состоит в свободном соединении одного члена с другим или группой других членов, если они связаны одинаковыми логическими операторами. В общем случае тернарная операция a*b*c называется ассоциативной, если a*(b*c)=(a*b)*c=(c*b)*a.
Ассоциативны шесть логических операций:
| (a&b)&c≡a&(b&c) | (aVb)Vc≡aV(bVc) | (aVb)Vc≡aV(bVc) |
| (a|b)|c≡a|(b|c) | (a↔b)↔c≡a↔(b↔c) | (a↓b)↓c≡a↓(b↓c) |
4.4. Закон дистрибутивности (распределительный закон). Дистрибутивность - отнесение признака к каждому предмету или понятию данного класса. Это свойство логических структур, основанное на сочетаемости разных логических операторов.
4.4.1. Дистрибутивность конъюнкции относительно слабой дизъюнкции для трёх переменных (операндов) распадается на три варианта:
| a&(bVc)≡(a&c)V(a&b) | b&(aVc)≡(a&b)V(b&c) | c&(bVa)≡(a&c)V(b&c) |
Доказательство всех трёх случаев с помощью электронной таблицы (на примере Microsoft Excel):
4.4.2. Дистрибутивность слабой дизъюнкции относительно конъюнкции для трёх переменных (операндов) распадается на три варианта:
| aV(b&c)≡(aVc)&(aVb) | bV(a&c)≡(aVb)&(bVc) | cV(b&a)≡(aVc)&(bVc) |
Доказательство всех трёх случаев с помощью электронной таблицы (на примере Microsoft Excel):
4.4.3. Дистрибутивно упорядочены пять пар логических операторов:
(aV(b⊃c))≡((aVb)⊃(aVc))(a⊃(bVc))≡((a⊃b)V(a⊃c))
(a⊃(b&c))≡((a⊃b)&(a⊃c))
(aV(b↔c))≡((aVb)↔(aVc))
(a⊃(b↔c))≡((a⊃b)↔(a⊃c))
4.5. Законы поглощения. Так называются равносильности
| a&(aVb)≡a | aV(a&b)≡a |
| a&(aV¬b)≡a | aV(a&¬b)≡a |
| ¬a&(¬aVb)≡¬a | ¬aV(¬a&b)≡¬a |
| ¬a&(¬aV¬b)≡¬a | ¬aV(¬a&¬b)≡¬a |
Частными случаями законов поглощения являются равносильности:
| ((¬aVb)&(¬aVbVc))≡¬aVb | ((aV¬b)&((aV¬b)V(a↔b)))≡aV¬b |
4.6. Законы идемпотентности (от лат. идемпотентный - сохраняющий ту же силу, способность). Этот закон утверждает, что конъюнкция двух или более тех же самых конъюнктов равносильна самому этому конъюнкту. То же справедливо и для дизъюнкции и составляющих её дизъюнктов. Законы идемпотентности записываются так:
| a&a≡a | aVa≡a |
4.7. Законы отбрасывания (исключения констант) позволяют исключать из формулы тавтологию и логическое противоречие.
4.7.1. Закон исключения тавтологии из конъюнкции : a&(bV¬b)≡a
4.7.2. Закон исключения противоречия из слабой дизъюнкции : aV(b&¬b)≡a
4.8.1. Законе (не)противоречия: a&¬a≡Л (иная запись: a&¬a≡0)
4.8.2. Законе исключённого третьего:aV¬a≡И (иная запись: aV¬a≡1)
4.9. Правила зачёркивания посылки:
| aV¬a&b≡aVb | ¬aVa&b≡¬aVb |
| a&(¬aVb)≡a&b | ¬a&(aVb)≡¬a&b |
| a&bV¬b≡aV¬b | a&(a⊃b)≡a&b |
4.10.Правила выявления:
| (aVb)&(¬bVc)≡(aVb)&(¬bVc)&(aVc) | a&bV¬b&c≡a&bV¬b&cVa&c |
| (aVb)&(¬aVc)≡(aVb)&(¬aVc)&(bVc) | a&bV¬a&c≡a&bV¬a&cVb&c |
| (aVb)&¬b≡(aVb)&a&¬b | a&(¬aVb)≡a&b&(¬aVb) |
4.11. Правила, вытекающие из табличных определений конъюнкции и слабой дизъюнкции:
 |
a&И≡a (или иначе a&1≡a) |  |
| aVЛ≡a (или иначе aV0≡a) | ||
| a&Л≡Л (или иначе a&0≡0) | ||
| aVИ≡И (или иначе aV1≡1) |
4.12. Законы общей инверсии (законы Огастеса де Моргана) позволяют выразить конъюнкцию через слабую дизъюнкцию и отрицание, а слабую дизъюнкцию - через конъюнкцию и отрицание: (aVb)≡¬a&¬b (a&b)≡¬aV¬b
4.13. Закон исключения (склеивания)
| для логического сложения | для логического умножения |
| (a&b)V(¬a&b)≡b | (aVb)&(¬aVb)≡b |
Сводная таблица логических операторов F1-F16 позволяет нам выражать одни операторы через другие. Например, закон общей инверсии (4.12) позволяет выразить логическое сложение через отрицание логического умножения, а логическое умножение - через отрицание и логическое сложение. Ранее мы уже выражали импликацию через отрицание и логическое сложение. Существуют такие пары операторов или одиночные операторы, которые могут через себя выразить все остальные, оставшиеся в таблице F1-F16.
Людям необходимо множество разных способов для выражения оттенков мыслей. Для вычислительной техники желательны устройства относительно простые и надёжные, унифицированные. Идеальный вариант - когда ЭВМ строится из одного универсального "кирпичика". Это приводит к тому, что высказывания внутри счётного цифрового устройства вырастают в длину. Для человека такой путь неприемлем.
Язык булевой алгебры, позволяющий выразить многообразие сочетаний пары операндов по истинности/ложности с помощью двух операторов (а лучше - одного), называется функционально полным. В двузначной логике таких языков насчитывается шесть. В фигурных скобках запишем один или два оператор(-а):
| ФПЯ I | ФПЯ III | ФПЯ V |
| {¬V} | {⊃V} | {|} |
| ФПЯ II | ФПЯ IV | ФПЯ VI |
| {¬&} | {⊃&} | {↓} |
Открытие функционально полных языков (далее - ФПЯ), состоящих из одного оператора, связано с тем, что некоторые из математиков, создававшие их, были глубоко верующими людьми. В теологии распространён постулат о том, что Господу для создания нашего мира из ничто ничего не надо было разрушать (отрицать). Он только творил (утверждал столп бытия). Это значило, что оператор инверсии (отрицания) можно было исключить из конструируемого языка, создать один из вариантов неотрицательной логики. Итак, получен довольно неожиданный вывод о том, что вычислительные машины в какой-то мере были созданы на основе религиозных представлений учёных мужей.
И в самом деле, импликация содержит в своём выходном столбце три утверждения и одно отрицание. По терминологии философов, отрицание в импликации "снято" (скрыто присутствует в логических значениях оператора). То же можно сказать о штрихе Шеффера (одно отрицание и три утверждения в выходном столбце) и о стрелке Пирса (одно утверждение и три отрицания).
В п. 3 на этой странице доказано, что a⊃¬b≡(a&b). Ещё выше было доказано, что a⊃b≡¬aVb. Это значит, что ФПЯ I можно выразить через ФПЯ III (и наоборот), ФПЯ II - через ФПЯ IV, ФПЯ I - через ФПЯ II (законы общей инверсии, 4.12.). Осталось доказать, что ФПЯ I, II, III, IV можно выразить через ФПЯ V или ФПЯ VI. Рассмотрим одно из следующих высказываний с помощью семантической таблицы:
Докажем, что 1) - 2) и 5)- 6)- попарно эквивалентные высказывания. Для утверждения 1) применим правило для штриха Шеффера: он ложен, когда оба его операнда истинны, в остальных случаях он истинный. Сделаем двумя входными столбцами операнд a. Для утверждения 2) применим правило для стрелки Пирса: она истинна, когда оба её операнда ложны, во всех остальных случаях она ложна. Для утверждений 3) и 4) применим правило: отрицание отрицания есть утверждение.
Докажем, что 3) - 4) - попарно эквивалентные высказывания.
Аналогично можно провести доказательства всех остальных случаев. Итак, действительно, через ФПЯ V и ФПЯ VI можно выразить все остальные операторы их сводной таблицы F1-F16.
Для конструирования устройств компьютера можно применять пять базовых элементов: инвертор, конъюнктор, дизъюнктор, "или-НЕ", "и-НЕ". Совмещая их по правилам ФПЯ I-VI, можно смоделировать работу любого оператора из сводной таблицы F1-F16.
 |
Построим логический контур для высказывания a&(bVc). Проанализируем структуру сложного высказывания. По приоритетам выполняется операция в скобках, а за ней - конъюнкция результата логического сложения и операнда а. Рассмотрим, какие сигналы поступят на выход этого устройства. Обозначим выход контура через F. Для логического сложения операндов b и c пользуемся правилом: логическое "ИЛИ" истинно, если хотя бы один из операндов истинный. Перемножение результата со столбцом a идёт по правилам логического "И". Выпишем на входах сигналы по первой строке семантической таблицы: a=0, b=0, c=0. Сигналы со входов b, c логически складываются в дизъюнкторе, затем с его выхода поступают на вход конъюнктора вместе с сигналом со входа а. |
 |
В конъюнкторе поступившие сигналы перемножаются и на его выходе получим 0. Заносим полученные значения в промежуточный и выходной столбцы. Переходим последовательно ко 2-й, 3-й и т.д. строкам семантической таблицы и заполняем промежуточный и выходной столбцы полученными логическими значениями. Таким способом можно наглядно рассмотреть, как проходят логический контур устройства разные сочетания сигналов.
По приведённому логическому контуру построим формулу сложного высказывания и его семантическую таблицу. Определим его имя по сводной таблице логических операторов F1-F16.
Формула сложного высказывания пишется как ¬a&¬b. В семантической таблице будет два операнда и четыре строки. В таблице понадобится два входных столбца, два промежуточных (для отрицаний) и выходной столбец, перемножающий сигналы с выходов инверторов.
|
Последовательно пошлём на входы устройства сочетания первой, затем второй и т. д. строк семантической таблицы, заполним промежуточные столбцы результатами действий инверторов. В выходном столбце заносим построчно результат работы конъюнктора. По сводной семантической таблице F1-F16 определяем, что это таблица функции "стрелка Пирса" (F9). Следовательно, данный нам логический контур моделирует работу по схеме логического оператора "или-НЕ". |
 |
Предлагаем самостоятельно исследовать работу контуров, приведённых ниже и опознать их по именам таблицы F1-F16.
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 | ||
Устройства внизу таблицы сделаны из однотипных логических элементов в соответствии с уже изученными формулами: (a↓a)↓(b↓b); (a|a)|(b|b). Сигналы на входы верхнего и нижнего устройств поступают в соответствии с сочетаниями входных столбцов a и b.
Ниже приводится таблица, содержащая диаграммы Эйлера-Венна ко всем операторам (функциям) таблицы F1-F16.
 |
 |
 |
 |
 |
 |
 |
 |
 |
|
 |
 |
 |
 |
 |
 |
Электронная схема устройства разработана в 1918 г. известным русским радиотехником М. А. Бонч-Бруевичем и независимо от него в 1919 г. американскими специалистами У. Икклзом и Ф. Джорданом. Рассмотрим простейшее устройство с двумя раздельными входами (RS-триггер). Эта схема составлена из двух вентилей "или-НЕ" (двух стрелок Пирса). Работа выхода P описывается уравнением P≡(S∨Q), выхода Q - уравнением Q≡(P∨R).
 | ||||
| Set | Reset | P | Q | Состояние триггера |
| 0 | 0 | 1 | 0 | Хранение бита |
| 0 | 1 | |||
| 0 | 1 | 1 | 0 | Запоминает 0 |
| 1 | 0 | 0 | 1 | Запоминает 1 |
| 1 | 1 | 0 | 0 | Комбинация не сохраняется |
Неустойчивое состояние: при действии входных импульсов на обоих входах (S=1, R=1) выходы определяются однозначно, но после прекращения действия входных импульсов такая комбинация входных величин сохраниться не может, и эта комбинация входных импульсов именуется запрещённой.
Устойчивые состояния: при отсутствии входных сигналов триггер будет находиться в одном из этих состояний, запоминая поданную на вход комбинацию. Одно из этих состояний называют нулевым (10), второе - единичным (01).
Если на входы этого триггера подать S=1, R=0, то (независимо от состояния Q) на выходе Р верхнего вентиля появится 0. После этого на входах нижнего вентиля окажется R=0, P=0 и выход Q станет равным 1.
Если теперь перестать подавать сигналы на триггер (S=0, R=0), то, поскольку входами верхнего вентиля являются S=0, Q=1, его выход Р останется 0. Аналогично, поскольку входами нижнего вентиля являются R=0 и Р=0, его выход Q по-прежнему будет 1. Таким образом, установленные значения выходов P и Q не изменятся при переходе к S=0, R=0.
Точно так же при подаче S=0, R=1 на выходах появятся Q=0, P=1 и эти значения входов сохранятся, если перестать подавать 1 на вход R (R=0, S=0). Подача сигнала на вход R позволяет вернуть триггер к исходному (нулевому) состоянию.
При отсутствии импульсных сигналов на обоих входах (S=0, R=0) выходные величины определяются неоднозначно: P=0, Q=1 либо P=1, Q=0. Это значит, что, пока на триггер не поступает входных импульсов, устройство сохраняет запомненную комбинацию.
Таким образом, при R=0, S=0 триггер на элементной базе "или-НЕ" может находиться в двух разных состояниях: Q=1 и Q=0. Выход Q и является значением запомненного бита.
Если собрать триггер из элементов "и-НЕ" (штриха Шеффера), то получим иное распределение на выходах устройства.
 | ||||
| Set | Reset | P | Q | Состояние триггера |
| 0 | 0 | 1 | 1 | Комбинация не сохраняется |
| 0 | 1 | 1 | 0 | Запоминает 0 |
| 1 | 0 | 0 | 1 | Запоминает 1 |
| 1 | 1 | 0 | 1 | Хранение бита |
| 1 | 0 |
В учебной литературе можно встретить два логических контура, описывающих полусумматор - устройство, суммирующее два одноразрядных двоичных числа без учёта переноса из младшего разряда. Они представляют собой зеркальные отражения друг друга.
 | ||||
| Слагаемые | Перенос | Сумма |  | |
| x | y | P | S | |
| 0 | 0 | 0 | 0 | |
| 0 | 1 | 0 | 1 | |
| 1 | 0 | 0 | 1 | |
| 1 | 1 | 1 | 0 | |
Работа этого устройства описывается для выхода Р уравнением P≡x&y, для выхода S - уравнением S≡(x∨y)&(x&y).
Построив таблицу истинности для выражения S, получим:
|
|
Изучение столбцов P и S показывает нам, что на входы x, y можно посылать двоичные сигналы 0 или 1 и получать на выходах P и S коды двоичных чисел 002, 012, 102. Полусумматор умеет складывать поступающие сигналы по правилам таблицы сложения для двоичной системы счисления и переносить результат сложения двух единиц в соседний (старший) разряд моделируемого двоичного числа.
 |
|
Сумматор на три входа (полный сумматор) назван так потому, что он может складывать три двоичных сигнала и выдавать на выходе сочетания 002, 012, 102, 112. Работа выхода Q определяется формулой x&P∨y&P∨x&y. Работа выхода S определяется формулой (¬Q∨x&y&P)&(x∨y∨P) [или ¬Q&(x∨y∨P)∨x&y&P]
Для того, чтобы понять, каким способом кодируются символы при вводе в компьютер, рассмотрим работу клавиатуры микрокалькулятора, а именно - его цифровые клавиши. Слева изображены кнопки цифр от 0 до 9. Нажимая на одну из них, человек замыкает цепь, посылая по контактному проводу сигнал на дизъюнкторы P, или Q, или R, или U. Предлагается самостоятельно рассмотреть работу шифратора при помощи такой таблицы:
Очевидно, что с помощью шифратора десятичные цифры можно ввести в вычислительное устройство сразу в двоичном коде.
©StavrosTektonos