Оглавление:

Закон логических операций

§ 3. Законы алгебры логики

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

Логические выражения, зависящие от одних и тех же логических переменных, называются равносильными, если на любом наборе значений переменных они принимают одинаковое значение (`0` или `1`). В дальнейшем для обозначения равносильности логических выражений мы будем использовать знак равенства.

это некоторые стандартные преобразования логических выражений, при которых сохраняется равносильность. Начнём с самых простых законов:

1) Законы поглощения констант

2) Законы поглощения переменных

3) Законы идемпотентности

4) Закон двойного отрицания

5) Закон противоречия

6) Закон исключённого третьего

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

Переходим к группе законов, которые практически аналогичны законам алгебры чисел.

7) Законы коммутативности

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

8) Законы ассоциативности

(x & y) & z = x & (y & z),

(x`vv`y) `vv` z = x `vv` (y `vv` z);

9) Законы дистрибутивности

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

Кроме аксиом и алгебраических свойств операций ещё существуют особые законы алгебры логики.

10) Законы де Моргана

`bar(x & y)= barx vv bary` ,

11) Загоны поглощения (не путать с аксиомами поглощения переменных нулём или единицей)

Рассмотрим пример доказательства первого закона де Моргана при помощи построения таблицы истинности.

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

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

Наше начальное выражение: x `vv` (x & y) . Выносим x за скобки и получаем следующее выражение:

x &(1 `vv` y) . Используем закон поглощения переменной константой `1` и получаем следующее выражение: x & 1. И теперь используем закон поглощения константы и получаем просто x .

В заключение, следует сказать несколько слов об операции импликации. Как уже отмечалось выше, импликация не обладает свойством коммутативности. Её операнды неравноправны, поэтому каждый из них имеет уникальное название. Левый операнд импликации называется посылкой, а правый – следствием. Из таблицы истинности импликации следует, что она истинна, когда истинно следствие, либо ложна посылка. Единственный случай, когда импликация ложна – это случай истинной посылки и ложного следствия. Таким образом, мы подошли к последнему закону алгебры логики, который бывает полезен при упрощении выражений.

12) Закон преобразования импликации

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

3) Дизъюнкция, строгая дизъюнкция, эквивалентность

zftsh.online

Малый математический факультет

Кубанского государственного университета

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

Прежде всего, начнем с разбора названия самого предмета, а именно выясним, каково значение алгебры, логики, а затем алгебры логики.

Алгебра – это раздел математики, предназначенный для описания действий над переменными величинами, которые принято обозначать строчными буквами латинского алфавита – а, b, x, y и т.д. Действия над переменными величинами записываются в виде математических выражений.

Термин «логика» происходит от древнегреческого “logos”, означающего «слово, мысль, понятие, рассуждение, закон».

Алгеброй логики называется аппарат, который позволяет выполнять действия над высказываниями.

Алгебру логику называют также алгеброй Буля, или булевой алгеброй, по имени английского математика Джорджа Буля, разработавшего в XIX веке ее основные положения. В булевой алгебре высказывания принято обозначать прописными латинскими буквами: A, B, X, Y. В алгебре Буля введены три основные логические операции с высказываниями? Сложение, умножение, отрицание. Определены аксиомы (законы) алгебры логики для выполнения этих операций. Действия, которые производятся над высказываниями, записываются в виде логических выражений.

Логические выражения могут быть простыми и сложными.

Простое логическое выражение состоит из одного высказывания и не содержит логические операции. В простом логическом выражении возможно только два результата — либо «истина», либо «ложь».

Сложное логическое выражение содержит высказывания, объединенные логическими операциями. По аналогии с понятием функции в алгебре сложное логическое выражение содержит аргументы, которыми являются высказывания.

В качестве основных логических операций в сложных логических выражениях используются следующие:

• НЕ (логическое отрицание, инверсия);

• ИЛИ (логическое сложение, дизъюнкция);

• И (логическое умножение, конъюнкция).

Логическое отрицание является одноместной операцией, так как в ней участвует одно высказывание. Логическое сложение и умножение — двуместные операции, в них участвует два выска¬зывания. Существуют и другие операции, например операции следования и эквивалентности, правило работы которых можно вывести на основании основных операций.

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

  • таблица истинности одноместной логической операции состоит из двух строк: два различных значения аргумента — «истина» (1) и «ложь» (0) и два соответствующих им значения функции;
  • в таблице истинности двуместной логической операции — четыре строки: 4 различных сочетания значений аргументов — 00, 01, 10 и 11 и 4 соответствующих им значения функции;
  • если число высказываний в логическом выражении N, то таблица истинности будет содержать 2 N строк, так как существует 2 N различных комбинаций возможных значений аргументов.

Операция НЕ — логическое отрицание (инверсия)

Логическая операция НЕ применяется к одному аргументу, в качестве которого может быть и простое, и сложное логическое выражение. Результатом операции НЕ является следующее:

• если исходное выражение истинно, то результат его отрицания будет ложным;

• если исходное выражение ложно, то результат его отрицания будет истинным.

Для операции отрицания НЕ приняты следующие условные обозначения:

Результат операции отрицания НЕ определяется следующей таблицей истинности:

mschool.kubsu.ru

Закон логических операций

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

Для определения истинности или ложности результатов логических операций пользуются таблицами истинности, где ИСТИНА и ЛОЖЬ обозначаются 1 и 0. Для логического сложения таблица истинности выглядит так:

II. Логическое умножение (конъюнкция).

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

Для логического умножения таблица истинности выглядит так:

III. Логическое отрицание (инверсия).

Присоединение частицы НЕ к сказуемому данного простого высказывания, называют логическим отрицанием или инверсией. Обозначают:

Для логического отрицания таблица истинности выглядит так:

IV. Логическое следование (импликация).

Сложное логическое высказывание , образованное с помощью связки ‘ЕСЛИ. ТО. ‘ называют логическим следованием или импликацией. Обозначают:

Для логического следования таблица истинности выглядит так:

V. Логическое равенство (эквивалентность).

Сложное логическое высказывание , образованное с помощью связки ‘ТОГДА И ТОЛЬКО ТОГДА. ‘ называют логическим равенством или эквивалентностью. Равнозначность называют также эквиваленцией. Обозначают:

Для логического равенства таблица истинности выглядит так:

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

Для логических операций порядок выполнения в заданной логической функции (составного высказывания) выглядит так:

Законы математической логики.

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



Виды задач по математической логике.

Составьте таблицу истинности для заданной функции:

Составим таблицу истинности для всех возможных значений высказываний, входящих в заданную функцию. Количество всех возможных значений определяется по формуле: 2 n , где n — количество входящих в функцию высказываний. Т.к. у нас в функцию входит только 2 высказывания — А и В, то возможных значений будет 2 2 = 4. Упрощаем работу, находя значения истинности функции по действиям. Порядок действий при этом надо соблюдать! Он как в математике:

Докажите равенство логических выражений с помощью таблиц истинности:

Составим таблицу истинности для обеих частей равенства, как в 1 задаче:

Сравним результаты в последних колонках. Если результаты совпали, то и функции равны.

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

Определите при каких значениях выражений заданная функция ложна:

1 способ: Составим полную таблицу истинности функции, как в 1 задаче:

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

2 способ: Заданная функция ложна только тогда, когда оба слогаемых ложны. Слогаемое ¬ (A /\ B) — ложно, если (A /\ B) — истинно. Произведение истинно, если оба сомножителя истинны, т. е. А=1 и В=1.

Ответ: при A=1 , B=1

Докажите равенство логических выражений с помощью законов математической логики:

Упращаем левое логическое выражение, пользуясь законами математической логики: непротиворечия и исключённого третьего

В результате пришли к виду правого логического выражения.

uchlogic.narod.ru

Закон логических операций

ТЕМА 7. ОСНОВЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ

7.1. Основные понятия формальной логики

Слово логика означает совокупность правил, которым подчиняется процесс мышления. Сам термин «логика» происходит от древнегреческого logos, означающего «слово, мысль, понятие, рассуждение, закон». Формальная логика — наука о формах и законах мышления. Законы логики отражают в сознании человека свойства, связи и отношения объектов окружающего мира. Логика как наука позволяет строить формальные модели окружающего мира, отвлекаясь от содержательной стороны. Основными формами мышления являются понятия, суждения и умозаключения.
Понятие — это форма мышления, которая выделяет существенные признаки предмета или класса предметов, отличающие его от других. Например, компьютер, человек, ученики.
Суждения — это форма мышления, в которой утверждается или отрицается связь между предметом и его признаком, отношения между предметами или факт существования предмета и которая может быть либо истинной, либо ложной. Языковой формой выражения суждения является повествовательное предложение. Вопросительные и побудительные предложения суждениями не являются.
Суждения рассматриваются не с точки зрения их смысла и содержания, а только с точки зрения их истинности или ложности. Истинным будет суждение, в котором связь понятий правильно отражает свойства и отношения реальных объектов. «Дважды два равно четырем» — истинное суждение, а вот «Процессор предназначен для печати» — ложное. Суждения могут быть простыми и сложными. «Весна наступила, и грачи прилетели» — сложное суждение, состоящее из двух простых. Простые суждения (высказывания) выражают связь двух понятий. Сложные — состоят из нескольких простых суждений.
Умозаключение — прием мышления, позволяющий на основе одного или нескольких суждений-посылок получить новое суждение (знание или вывод).
Примерами умозаключений являются доказательства теорем в геометрии. Посылками умозаключения по правилам формальной логики могут быть только истинные суждения. Тогда и умозаключение будет истинным. Иначе можно прийти к ложному умозаключению.
Математическая логика изучает вопросы применения математических методов для решения логических задач и построения логических схем, которые лежат в основе работы любого компьютера. Суждения в математической логике называют высказываниями или логическими выражениями. Подобно тому, как для описания действий над переменными был разработан раздел математики алгебра, так и для обработки логических выражений в математической логике была создана алгебра высказываний, или алгебра логики.

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

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

Связки «НЕ», «И», «ИЛИ» заменяются логическими операциями инверсия, конъюнкция, дизъюнкция. Это основные логические операции, при помощи которых можно записать любое логическое выражение.
Логическое отрицание (инверсия).
В обыденной речи мы часто пользуемся словом «НЕ», или словами «НЕВЕРНО, ЧТО», когда хотим что-то отрицать. Пусть, например, кто-то сказал: «Тоска зеленая.» (Обозначим это высказывание А). Если Вы не согласны, Вы скажете:» Тоска НЕ зеленая.» Или:» Неверно, что тоска зеленая.» (Ваше высказывание обозначим В). Нетрудно заметить, что значения истинности высказываний А и В находятся в определенной связи: если А истинно, то В ложно, и наоборот. Операция, с помощью которой из высказывания А получается высказывание В, называется логическим отрицанием и само высказывание В называется отрицанием высказывания А и обозначается ¬ А.
Таким образом, отрицанием ¬ А некоторого высказывания А называется такое высказывание, которое истинно, когда А ложно, и ложно, когда А истинно. Отрицание высказывания А обозначим ¬А. Определение отрицания может быть записано с помощью так называемой таблицы истинности:

В ней указано, какие значения истинности (Истина, Ложь) принимает отрицание ¬ А в зависимости от значений истинности исходного высказывания А.

Логическое умножение (конъюнкция) от латинского conjunctio — союз, связь.
Если два высказывания соединены союзом «И», то полученное сложное высказывание обычно считается истинным тогда и только тогда, когда истинны оба составляющие его высказывания. Если хотя бы одно из составляющих высказываний ложно, то и полученное из них с помощью союза «И» сложное высказывание также считается ложным. Например, возьмем два высказывания: «У кота есть хвост» (А), «У зайца есть хвост» (В). Сложное высказывание «У кота есть хвост и у зайца есть хвост» истинно, т.к. истинны оба высказывания А и В. Но если взять другие высказывания: «У кота длинный хвост» (С), «У зайца длинный хвост» (D), то сложное высказывание «У кота длинный хвост и у зайца длинный хвост» будет ложным, т.к. ложно высказывание (D). Таким образом, исходя из обычного смысла союза «И», приходим к определению соответствующей логической операции — конъюнкции.
Таким образом, конъюнкцией двух высказываний А и В называется такое высказывание, которое истинно тогда и только тогда, когда истинны оба высказывания А и В.
Конъюнкцию высказываний А и В мы обозначим: A & B. Знак & — амперсент — читается как английское «and» (помните Procter & Gamble или Wash & Go?). Часто встречается обозначение А Λ В. Иногда, для краткости, пишут просто АВ.
Определение конъюнкции может быть записано в виде таблицы истинности, в которой для каждого из четырех возможных наборов значений исходных высказываний А и В задается соответствующее значение конъюнкции А & В:

Определение конъюнкции двух высказываний естественным образом распространяется на любое конечное число составляющих: конъюнкция А1 & A2 & A3 &. & AN истинна тогда и только тогда, когда истинны все высказывания А1, A2, A3, . AN (а, следовательно, ложна, когда ложно хотя бы одно из этих высказываний).
Логическое сложение (дизъюнкция) от латинского disjunctio — разобщение, различие.
Если два высказывания соединены союзом «ИЛИ», то полученное сложное высказывание обычно считается истинным, когда истинно хотя бы одно из составляющих высказываний. Например, возьмем два высказывания: «Мел черный.» (А), «Доска черная.» (В). Высказывание «Мел черный или доска черная» будет истинным, т.к. одно из исходных высказываний (В) истинно.
Таким образом, дизъюнкцией двух высказываний называется такое новое высказывание, которое истинно тогда и только тогда, когда истинно хотя бы одно из этих высказываний.
Дизъюнкцию высказываний А и В мы обозначим символом А V В и будем читать: А или В. Определение дизъюнкции может быть записано в виде таблицы истинности:

Определение дизъюнкции двух высказываний естественным образом распространяется на любое конечное число составляющих: дизъюнкция А1 V А2 V А3 V. V АN истинна тогда и только тогда, когда истинно хотя бы одно из высказываний А1, А2, А3, . АN (а следовательно, ложна, когда ложны все эти высказывания).
Логическое следование (импликация) от латинского implico — тесно связываю.
В наших рассуждениях, особенно в математических доказательствах, мы часто пользуемся сложными высказываниями, образованными с помощью слов «если. то. «. Здесь высказывание, расположенное после слова «если», называется основанием или посылкой, а высказывание, расположенное после слова «то», называется следствием или заключением.
Рассмотрим пример: из арифметики. Вам должно быть известно, что утверждение «если каждое слагаемое делится на 3, то и сумма делится на 3» истинно, т.е. из высказывания «каждое слагаемое делится на 3» следует высказывание «сумма делится на 3». Посмотрим, какие наборы значений истинности посылки и заключения возможны, когда истинно все утверждение. Возьмем, например, в качестве слагаемых числа 6 и 9. В этом случае истинны и посылка, и заключение, и все утверждение. Если же взять числа 4 и 5, то посылка будет ложной, а заключение истинным. Для чисел 4 и 7 и посылка и заключение ложны. (Если Вы сомневаетесь в истинности высказывания для последнего случая попробуйте произнести его в сослагательном наклонении: если бы числа 4 и 7 делились бы на 3, то и их сумма делилась бы на 3). Очевидно, что только один случай невозможен: мы не найдем таких двух слагаемых, чтобы каждое из них делилось на 3, а их сумма не делилась на 3, т.е. чтобы посылка была истинной, а заключение ложным. Из истины не может следовать ложь, иначе логика теряет смысл. Высказывание «Если А, то В» с логической точки зрения имеет тот же смысл, что и высказывание «неверно, что А истинно и В ложно». Это означает, что функцию импликации можно заменить комбинацией двух функций (отрицания и конъюнкции). Обычно, когда мы хотим установить ложность высказывания «Если А, то В«, мы стараемся показать, что возможен случай, когда А истинно, а В ложно (доказательство «от противного»). Обозначим импликацию символом => и запись «А => В» будем читать: «Из А следует В«.
Таким образом, импликацией А => В называется высказывание, которое ложно тогда и только тогда, когда А истинно и В ложно.
Запишем это определение в виде таблицы истинности:

Логическое тождество (эквиваленция).
Интуитивно можно догадаться, что высказывания эквивалентны (равносильными), когда их значения истинности одинаковы. Например, эквивалентны высказывания: «железо тяжелое» и «пух легкий», так же как и высказывания: «железо легкое» и «пух тяжелый». Обозначим эквиваленцию символом и запись «А В» будем читать «А эквивалентно В«, или «А равносильно В«, или «А, если и только если В«.
Таким образом, эквиваленцией двух высказываний А и В называется такое высказывание, которое истинно тогда и только тогда, когда оба эти высказывания А и В истинны или оба ложны.
Отметим, что высказывание типа «А, если и только если В» можно заменить высказыванием «Если А, то В и, если В, то А» (обдумайте это на досуге и обратите внимание на символ ). Следовательно, функцию эквиваленции можно заменить комбинацией функций импликации и конъюнкции. Запишем таблицу истинности для эквиваленции:

7.3. Построение таблиц истинности для логических функций

Логическая функция — это функция, в которой переменные принимают только два значения: логическая единица или логический ноль. Истинность или ложность сложных суждений представляет собой функцию истинности или ложности простых. Эту функцию называют булевой функцией суждений f (a, b).
Любая логическая функция может быть задана с помощью таблицы истинности, в левой части которой записывается набор аргументов, а в правой части — соответствующие значения логической функции.
При построении таблицы истинности необходимо учитывать порядок выполнения логических операций. Операции в логическом выражении выполняются слева направо с учетом скобок в следующем порядке:
1. инверсия;
2. конъюнкция;
3. дизъюнкция;
4. импликация и эквивалентность.
Для изменения указанного порядка выполнения логических операций используются круглые скобки.
Предлагается следующий алгоритм построения таблицы истинности.
1. Определить количество наборов входных переменных — всевозможных сочетаний значений переменных, входящих в выражения, по формуле: Q=2 n , где n — количество входных переменных. Оно определяет количество строк таблицы.
2. Внести в таблицу все наборы входных переменных.
3. Определить количество логических операций и последовательность их выполнения.
4. Заполнить столбцы результатами выполнения логических операций в обозначенной последовательности.

Чтобы не повторить или не пропустить ни одного возможного сочетания значений входных переменных, следует пользоваться одним из предлагаемых ниже способов заполнения таблицы.
Способ 1. Каждый набор значений исходных переменных есть код числа в двоичной системе счисления, причем количество разрядов числа равно количеству входных переменных. Первый набор — число 0. Прибавляя к текущему числу каждый раз по 1, получаем очередной набор. Последний набор — максимальное значение двоичного числа для данной длины кода.
Например, для функции от трех переменных последовательность наборов состоит из чисел:

Способ 2. Для функции от трех переменных последовательность данных можно получить следующим путем:
а) разделить колонку значений первой переменной пополам и заполнить верхнюю половину нулями, нижнюю половину единицами;
б) в следующей колонке для второй переменной половинку снова разделить пополам и заполнить группами нулей и единиц; аналогично заполнить вторую половинку;
в) так делать до тех пор, пока группы нулей и единиц не будут состоять из одного символа.
Способ 3. Воспользоваться известной таблицей истинности для двух аргументов. Добавляя третий аргумент, сначала записать первые 4 строки таблицы, сочетая их со значением третьего аргумента, равным 0, а затем еще раз записать эти же 4 строки, но теперь уже со значением третьего аргумента, равным 1. В результате в таблице для трех аргументов окажется 8 строк:

Например, построим таблицу истинности для логической функции:

Количество входных переменных в заданном выражении равно трем (A,B,C). Значит, количество входных наборов Q=2 3 =8.
Столбцы таблицы истинности соответствуют значениям исходных выражений A,B,C, промежуточных результатов и (B V C), а также искомого окончательного значения сложного арифметического выражения :

7.4. Логические функции и их преобразования. Законы логики

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

Основываясь на законах, можно выполнять упрощение сложных логических выражений. Такой процесс замены сложной логической функции более простой, но равносильной ей, называется минимизацией функции.
Пример 1. Упростить выражения так, чтобы в полученных формулах не содержалось отрицания сложных высказываний.
Решение

Пример 2. Минимизировать функцию

Решение

При упрощении выражения использовались формулы поглощения и склеивания.
Пример 3. Найти отрицание следующего высказывания: «Если урок будет интересным, то никто из учеников (Миша, Вика, Света) не будет смотреть в окно».
Решение
Обозначим высказывания:
Y — «Урок интересный»;
M — «Миша смотрит в окно»;
B — «Вика смотрит в окно»;
C — «Света смотрит в окно».

При упрощении выражения использовались формула замены операций и закон де Моргана.
Пример 4. Определить участника преступления, исходя из двух посылок:
1) «Если Иванов не участвовал или Петров участвовал, то Сидоров участвовал»;
2) «Если Иванов не участвовал, то Сидоров не участвовал».
Решение
Составим выражения:
I — «Иванов участвовал в преступлении»;
P — «Петров участвовал в преступлении»;
S — «Сидоров участвовал в преступлении».
Запишем посылки в виде формул:

Тогда

Проверим результат, используя таблицу истинности:

Ответ: Иванов участвовал в преступлении.

Построение логической функции по ее таблице истинности
Мы научились составлять таблицу истинности для логической функции. Попробуем решить обратную задачу. Пусть дана таблица истинности для некоторой логической функции Z(X,Y):

Рассмотрим строки, где значение истинности функции Z истинно (Z=1). Функцию для этой таблицы истинности можно составить следующим образом: Z(X,Y) = (¬ X& ¬Y)V(X& ¬Y).
Каждой строке, где функция истинна (равна 1), соответствует скобка, представляющая собой конъюнкцию аргументов, причем если значение аргумента О, то мы берем его с отрицанием. Все скобки соединены между собой операцией дизъюнкции. Полученную формулу можно упростить, применив законы логики:
Z(X,Y) ((¬X& ¬Y) VX)&(( ¬X&Y)V ¬Y) (XV( ¬X& ¬Y)) &( ¬YV(¬X&¬Y)) ((XV¬X)&(XV ¬Y))&(( Y¬V ¬X)&( ¬YV ¬Y)) (1&(XV ¬Y))&(( ¬YV ¬X)& ¬Y) (XV ¬Y)&(( ¬YV ¬X)& ¬Y).
Проверьте полученную формулу: составьте таблицу истинности для функции Z(X,Y).
Запишите правила конструирования логической функции по ее таблице истинности:
1. Выделить в таблице истинности те строки, в которых значение функции равно 1.
2. Выписать искомую формулу в виде дизъюнкции нескольких логических элементов. Число этих элементов равно числу выделенных строк.
3. Каждый логический элемент в этой дизъюнкции записать в виде конъюнкции аргументов функции.
4. Если значение какого-либо аргумента функции в соответствующей строке таблице равно 0, то этот аргумент мы берем с отрицанием.

7.5. Построение логических схем

Знания из области математической логики можно использовать для конструирования электронных устройств. Нам известно, что 0 и 1 в логике не просто цифры, а обозначение состояний какого-то предмета нашего мира, условно называемых «ложь» и «истина». Таким предметом, имеющим два фиксированных состояния, может быть электрический ток. Устройства, фиксирующие два устойчивых состояния, называются бистабильными (например, выключатель, реле). Если вы помните, первые вычислительные машины были релейными. Позднее были созданы новые устройства управления электричеством — электронные схемы, состоящие из набора полупроводниковых элементов. Такие электронные схемы, которые преобразовывают сигналы только двух фиксированных напряжений электрического тока (бистабильные), стали называть логическими элементами.
На элементарном уровне конъюнкцию можно представить себе в виде последовательно соединенных выключателей, а дизъюнкцию — в виде параллельно соединенных выключателей:

Логические элементы имеют один или несколько входов и один выход, через которые проходят электрические сигналы, обозначаемые условно 0, если «отсутствует» электрический сигнал, и 1, если «имеется» электрический сигнал. Простейшим логическим элементом является инвертор, выполняющий функцию отрицания. Если на вход поступает сигнал, соответствующий 1, то на выходе будет 0. И наоборот. У этого элемента один вход и один выход. На функциональных схемах он обозначается:

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

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

Специальных логических элементов для импликации и эквивалентности нет, т.к. А => В можно заменить на ¬А V В ; А В можно заменить на (A & B)V(¬A & ¬B).
Другие логические элементы построены из этих трех простейших и выполняют более сложные логические преобразования информации. Сигнал, выработанный одним логическим элементом, можно подавать на вход другого элемента, это дает возможность образовывать цепочки из отдельных логических элементов. Например:

Эта схема соответствует сложной логической функции F(A,B)= ¬ (А V В).
Попробуйте проследить изменения электрического сигнала в этой схеме. Например, какое значение электрического сигнала (0 или 1) будет на выходе, если на входе: А=1 и В=0.
Такие цепи из логических элементов называются логическими устройствами. Логические устройства же, соединяясь, в свою очередь образуют функциональные схемы (их еще называют структурными или логическими схемами). По заданной функциональной схеме можно определить логическую формулу, по которой эта схема работает, и наоборот.
Пример 1. Логическая схема для функции будет выглядеть следующим образом:

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

Решение
По таблице построим СДНФ логической функции и упростим ее:

Правильность полученной формулы можно проверить, составив для нее таблицу истинности:

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

Рассмотрим еще два логических элемента, которые играют роль базовых при создании более сложных элементов и схем.

Логический элемент И-НЕ состоит из конъюнктора и инвертора:
Выходная функция выражается формулой .
Логический элемент ИЛИ-НЕ состоит из дизъюнктора и инвертора:

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

7.6. Логическая реализация типовых устройств компьютера

Обработка любой информации на компьютере сводится к выполнению процессором различных арифметических и логических операций. Для этого в состав процессора входит так называемое арифметико-логическое устройство (АЛУ). Оно состоит из ряда устройств, построенных на рассмотренных выше логических элементах. Важнейшими из таких устройств являются триггеры, полусумматоры, сумматоры, шифраторы, дешифраторы, счетчики, регистры.
Этапы конструирования логического устройства.
Конструирование логического устройства состоит из следующих этапов:
1. Построение таблицы истинности по заданным условиям работы проектируемого узла (т.е. по соответствию его входных и выходных сигналов).
2. Конструирование логической функции данного узла по таблице истинности, ее преобразование (упрощение), если это возможно и необходимо.
3. Составление функциональной схемы проектируемого узла по формуле логической функции.
После этого остается только реализовать полученную схему.
Попробуем, действуя по этому плану, сконструировать устройство для сложения двух двоичных чисел (одноразрядный полусумматор).
Пусть нам необходимо сложить двоичные числа X и Y. Через P и Z обозначим первую и вторую цифру суммы: X + Y = PZ. Вспомните таблицу сложения двоичных чисел.
1. Таблица истинности, определяющая результат сложения, имеет вид:

2. Сконструируем функции P(X,Y) и Z(X,Y) по этой таблице:
P(X,Y)=X & Y; Z(X,Y)=(¬ X&Y)V (X& ¬ Y).
Преобразуем вторую формулу, пользуясь законами логики.
(¬ X&Y)V(X& ¬Y) ((¬ X&Y)VX)& ((¬ X&Y)V ¬Y) (XV(¬ X&Y))&(¬ YV (Y& ¬X)) ((XV ¬X)&(XVY))& ((¬ YVY)&(¬ Y V ¬X)) (1&(XVY))&((И& ¬(X&Y)) (XVY)& ¬(X&Y).

3. Теперь можно построить функциональную схему одноразрядного полусумматора:

Одноразрядный двоичный сумматор на три входа и два выхода называется полным одноразрядным сумматором.
Сумматор — это электронная логическая схема, выполняющая суммирование двоичных чисел поразрядным сложением. Сумматор является центральным узлом арифметико-логического устройства процессора. Находит он применение и в других устройствах компьютера. Сумматор выполняет сложение многозначных двоичных чисел. Он представляет собой последовательное соединение одноразрядных двоичных сумматоров, каждый из которых осуществляет сложение в одном разряде. Если при этом возникает переполнение разряда, то перенос суммируется с содержимым старшего соседнего разряда.
Общая схема сумматора:

Триггер — электронная схема, применяемая для хранения значения одноразрядного двоичного кода.
Воздействуя на входы триггера, его переводят в одно из двух возможных состояний (0 или 1). С поступлением сигналов на входы триггера в зависимости от его состояния либо происходит переключение, либо исходное состояние сохраняется. При отсутствии входных сигналов триггер сохраняет свое состояние сколь угодно долго.
Термин триггер происходит от английского слова trigger — защёлка, спусковой крючок. Для обозначения этой схемы в английском языке чаще употребляется термин flip-flop, что в переводе означает «хлопанье». Это звукоподражательное название электронной схемы указывает на её способность почти мгновенно переходить («перебрасываться») из одного электрического состояния в другое.
Существуют разные варианты исполнения триггеров в зависимости от элементной базы (И-НЕ, ИЛИ-НЕ) и функциональных связей между сигналами на входах и выходах (RS, JK, T, D и другие).
Самый распространённый тип триггера — это RS-триггер (S и R соответственно от английских set — установка, и reset — сброс). Условное обозначение RS-триггера:

Триггер имеет два симметричных входа S и R, которые используются для установки в единичное состояние и сброса, — в нулевое. Еще у него есть два симметричных выхода Q и , причем выходной сигнал Q является логическим отрицанием сигнала .
За единичное состояние триггера условились принимать такое, при котором Q=1.
На каждый из входов S и R могут подаваться входные сигналы в виде кратковременных импульсов . Наличие импульса на входе считается единицей, а его отсутствие — нулем.
Ниже показана схема реализации триггера с помощью элементов ИЛИ-НЕ и соответствующая таблица истинности.

Два одинаковых двухвходовых логических элемента ИЛИ-НЕ соединены симметричным образом. Сигнал, поданный на один из входов каждого элемента, снимается с выхода другого. Наличие такого соединения и дает триггеру возможность сохранять свое состояние после прекращения действия сигналов (никакой другой логический элемент не в состоянии поддерживать сигнал на выходе после прекращения действия входного напряжения).
Проанализируем возможные комбинации значений входов R и S триггера, используя его схему и таблицу истинности схемы.
1. Пусть поданы сигналы S=1, R=0. Независимо от состояния другого входа на выходе верхнего элемента появится 0. Этот нулевой сигнал подается на вход нижнего элемента, где уже есть R=0. Выход нижнего элемента станет равным 1. Эта единица возвращается на вход первого элемента. Теперь состояние другого входа (S) этого элемента роли не играет: если даже убрать входной сигнал S, состояние триггера останется без изменения. Поскольку Q=1, триггер перешел в единичное состояние, устойчивое, пока не придут новые внешние сигналы.
2. При S=0 и R=1 вследствие симметричности схемы все происходит аналогично, но теперь на выходе Q будет 0. То есть при подаче сигнала на вход R триггер сбрасывается в устойчивое нулевое состояние.
3. При окончании действия обоих сигналов (R=0 и S=0) триггер сохраняет на выходе Q тот сигнал, который был установлен входным импульсом S или R.
4. Подача импульсов одновременно на входы R и S может привести к неоднозначному результату, поэтому эта комбинация входных сигналов (R=1 и S=1) запрещена.
Один триггер хранит один бит информации. Для хранения одного байта информации необходимо 8 триггеров. Современные микросхемы памяти содержат миллионы триггеров.
По технологии изготовления память делится на статическую и динамическую. На триггерах основана статическая память, а динамическая устроена по принципу конденсатора: заряженный конденсатор соответствует единице, а незаряженный — нулю.
Динамическая память проще по устройству, имеет больший объем и дешевле. В силу этих преимуществ в настоящее время основной объем оперативного запоминающего устройства компьютера является динамическим.
Однако статическая память имеет более высокое быстродействие. Кэш-память имеет статическую природу, что позволяет согласовать высокое быстродействие процессора и низкую скорость работы динамической памяти.
Конденсаторы динамической памяти постепенно разряжаются через внешние цепи, и потому требуют периодичекой подзарядки, чтобы не потерять информацию. Этот процесс называется регенерацией памяти, его наличие усложняет подключение микросхем динамической памяти. Микросхема статической памяти сильнее нагревается при работе, так как использует активные элементы — транзисторы.
Некоторое количество триггеров, объединенных вместе общей системой управления, называется регистром. Регистры содержатся в различных вычислительных узлах компьютера — процессоре, периферийных устройствах и т.д. Регистр — это устройство, предназначенное для хранения многоразрядного двоичного числового кода, которым можно представлять и адрес, и команду, и данные.
Упрощенно регистр можно представить как совокупность ячеек, в каждой из которых может быть записано одно из двух значений: 0 или 1, то есть один разряд двоичного числа.
Существует несколько типов регистров, отличающихся видом выполняемых операций. Некоторые важные регистры имеют свои названия, например:
сдвиговый регистр — предназначен для выполнения операции сдвига;
счетчики — схемы, способные считать поступающие на вход импульсы. К ним относятся Т-триггеры (название от англ. tumble — опрокидываться). Этот триггер имеет один счетный вход и два выхода. Под действием сигналов триггер меняет свое состояние с нулевого на единичное и наоборот. Число перебрасываний соответствует числу поступивших сигналов;
счетчик команд — регистр устройства управления процессора (УУ), содержимое которого соответствует адресу очередной выполняемой команды; служит для автоматической выборки программы из последовательных ячеек памяти;
регистр команд — регистр УУ для хранения кода команды на период времени, необходимый для ее выполнения. Часть его разрядов используется для хранения кода операции, остальные — для хранения кодов адресов операндов.
Техническая сторона логики компьютера основана на технологии транзистора, что позволяет получать одну из двух возможных единиц информации (0 и 1), оперируя с передачей или отсутствием передачи тока. На следующем уровне вступает система носителей (переносчиков) информации — это нули и единицы (0 и 1), которые отражают в себе реальную информацию путем применения, как систем счисления, так и системы команд микропроцессора.
Логика микропроцессора (МП). МП имеет (может иметь) встроенную логику, основанную на формальной логике человека. Таким образом, имеется возможность обрабатывать информацию. Так, например, получая группу информационных потоков (два потока), МП может, используя формальную логику, выдать один искомый поток.
Логика операционной системы. Хотя технически возможна работа на компьютере без использования операционной системы (ОС), так как в ПЗУ находятся (могут находиться) для этого специальные программы, целесообразность использования ОС никем не подвергается сомнению. ОС представляет собой программу (группу программ), которая обеспечивает полный системный интерфейс компьютера.
И, наконец, логика прикладных программ. В данном случае все зависит от фантазии и профессионализма программиста или пользователя.
Проиллюстрируем уровни логики ЭВМ. Получив на два регистра по единице и команду реализовать функцию AND, МП, применив заложенную в нем формальную логику, выдает на результирующий регистр единицу. Эта единица некоторым образом интерпретируется операционной системой, например, как истинность выполненной операции, а затем передается (может передаваться) прикладной программе, которая в свою очередь так же интерпретирует полученную информацию и производит в соответствии с этим некоторые действия.

www.ido.rudn.ru

Еще по теме:

  • Нотариус на шокальского 3 корп 1 Нотариусы Москвы, Северо-Восточный автономный округ Нотариальные конторы СВАО, Северо-Восточный автономный округ Иванова В. В. Метро: Алексеевская, 500м 1 2 9 0 8 5 Москва, Звездный бульвар, д.19, оф.106 Орлова Д. В. Метро: Алексеевская, 800м 1 2 9 […]
  • Нотариус на ореховом бульваре 31 Нотариусы Москвы на станции метро Домодедовская Ниже представлен список нотариусов в выбранной категории. Чтобы посмотреть подробную информацию по конкретному нотариусу, кликните по ФИО нотариуса. Нотариус Гончарова Любовь Львовна Телефон: […]
  • Статья 166 часть 3 ук Статья 166 часть 3 ук Статья 166. Неправомерное завладение автомобилем или иным транспортным средством без цели хищения 1. Неправомерное завладение автомобилем или иным транспортным средством без цели хищения (угон) - наказывается штрафом в […]
  • Заявление от работника на уменьшение ндфл Иностранный работник: уменьшаем НДФЛ на фиксированный авансовый платеж Работодатель — налоговый агент имеет право на уменьшение НДФЛ иностранного работника на сумму фиксированных авансовых платежей, уплаченных им самостоятельно. Рассмотрим порядок […]
  • Примеры для законов диалектики Диалектика в нашей жизни Диалектика в нашей жизни (из записок пессимиста) Пессимист – это хорошо информированный оптимист (народная мудрость) Что такое диалектика и какие ее основные законы лучше всего знают люди, получившие образование во времена […]
  • Краснинский суд Краснинский районный суд Смоленской области 5 января 1923 года президиум Смоленского губисполкома заслушал доклад о реорганизации судебных органов губернии и постановил упразднить с 1 января 1923 года Совнарсуд, Губревтрибунал и особые Сессии […]