Определите какой логической операции соответствует таблица истинности: 404 | Университет СИНЕРГИЯ — RC74 — интернет-магазин радиоуправляемых моделей

Содержание

Логические операции и таблицы истинности

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

1. Отрицание.

Эта логическая операция соответствует в обыденной жизни частице «не».

Определение. Отрицанием высказывания x называется новое высказывание, которое является истинным, если высказывание ложно, и ложным, если высказывание x истинно.

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

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

2. Дизъюнкция (логическое сложение).

Эта логическая операция соответствует союзу «или».

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

Дизъюнкция высказываний x, y обозначается xy и читается «x или y». Логические значения дизъюнкции описываются таблицей истинности:

Высказывания x, y называются членами дизъюнкции.

Пример.

x – «5>3», y – «2>4». Тогда xy – «5>3»«2>4» истинно, так как истинно высказывание x.

В алгебре логики союз «или» всегда употребляется в неисключающем смысле. Из определения дизъюнкции и отрицания следует, что высказывание x всегда истинно.

3. Конъюнкция.

Эта логическая операция соответствует союзу «и».

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

Конъюнкция высказываний x, y обозначается и читается «x и y». Высказывания x, y называются членами конъюнкции. Логические значения конъюнкции описываются следующей таблицей истинности:

Пример.

x – «6 делится на 2», y – «6 делится на 3». Тогда – «6 делится на 2»«6 делится на 3» истинно.

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

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

4. Импликация.

Эта логическая операция соответствует словам «если…,то…».

Определение. Импликацией двух высказываний x, y называется новое высказывание, которое считается ложным, если x истинно, а y ложно, и истинным во всех остальных случаях.

Импликация высказываний обозначается x→y и читается «если x, то y» или «из x следует y». Высказывание x называется условием или посылкой, а высказывание y – следствием или заключением. Высказывание x→y называется следованием или импликацией. Логические значения операции импликации описываются следующей таблицей истинности:

x→y

Пример.

1) x – «12 делится на 6», y – «12 делится на 3». Тогда импликация x→y – «если 12 делится на 6, то оно делится на 3» истинна, так как истинна посылка x, и истинно заключение y.

2) x – «12 делится на 2 и 3», y – «12 делится на 7». Тогда импликация x→y – «если 12 делится на 2 и 3, то оно делится на 7» ложна, так как условие истинно, а заключение ложно.

Употребление слов «если…,то…» в алгебре логики отличается от употребления их в обыденной речи, когда, как правило, считается, что если высказывание x ложно, то высказывание «если x, то y» вообще не имеет смысла. Кроме того, строя предложение «если x, то y» в обыденной речи всегда подразумевается, что предложение y вытекает из предложения x. Употребление слов «если…, то…» в математической логике не требует этого, так как в ней смысл высказываний не рассматривается.

Импликация играет важную роль в математических доказательствах, так как многие теоремы формулируются в условной форме «если x, то y». Если при этом известно, что x истинно и доказана истинность импликации x→y то истинно и заключение y. В этом случае пишут xy и говорят, что из x следует y. Это классическое правило вывода постоянно используется в математике.

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

Эта логическая операция соответствует словам «тогда и только тогда, когда».

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

Эквиваленция высказываний x, y обозначается символом x↔y и читается «для того чтобы x, необходимо и достаточно, чтобы y» или «x тогда и только тогда, когда y». Логические значения операции эквиваленции описываютсяследующей таблицей истинности:

x↔y

Высказывания x, y называются членами эквиваленции.

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

Таблица истинности — таблица, показывающая, какие значения принимает составное высказывание при всех сочетаниях (наборах) значений входящих в него простых высказываний.

Логическое выражение — составные высказывания в виде формулы.

Равносильные логические выражения – логические выражения, у которых последние столбцы таблиц истинности совпадают. Для обозначения равносильности используется знак «=».

Алгоритм построения таблицы истинности:

1. подсчитать количество переменных n в логическом выражении;

2. определить число строк в таблице по формуле m=2ⁿ, где n — количество переменных;

3. подсчитать количество логических операций в формуле;

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

5. определить количество столбцов: число переменных + число операций;

6. выписать наборы входных переменных;

7. провести заполнение таблицы истинности по столбцам, выполняя логические операции в соответствии с установленной в пункте 4 последовательностью.

Заполнение таблицы:

1. разделить колонку значений первой переменной пополам и заполнить верхнюю часть «0», а нижнюю «1»;

2. разделить колонку значений второй переменной на четыре части и заполнить каждую четверть чередующимися группами «0» и «1», начиная с группы «0»;

3. продолжать деление колонок значений последующих переменных на 8, 16 и т.д. частей и заполнение их группами «0» или «1» до тех пор, пока группы «0» и «1» не будут состоять из одного символа.

Пример 1. Для формулы A/\ (B \/ ¬B /\¬C) постройте таблицу истинности.

Количество логических переменных 3, следовательно, количество строк — 2³ = 8.

Количество логических операций в формуле 5, количество логических переменных 3, следовательно количество столбцов — 3 + 5 = 8.

Пример 2. Определите истинность логического выражения F(А, В) = (А\/ В)/\(¬А\/¬В) .

1. В выражении две переменные А и В (n=2).

2. m_строк=2ⁿ, m=2²=4 строки.

3. В формуле 5 логических операций.

4. Расставляем порядок действий

1) А\/ В; 2) ¬А; 3) ¬В; 4) ¬А\/¬В; 5) (А\/ В)/\(¬А\/¬В).

5. К_{столбцов}=n+5=2+5=7 столбцов.

А\/ В

¬А

¬В

¬А\/¬В

Вывод: логическое выражение принимает значение истина при наборах F(0,1)=1 и F(1,0)=1.

Пример 3. Построёте таблицу истинности для логического выражения

F = (A\/ B) /\ ¬С

В данной функции три логические переменные – А, В, С
количество строк таблицы = 2³=8
В формуле 3 логические операции.
Расставляем порядок действий

1) А\/ В; 2) ¬С; 3) (AVB) /\ ¬С .

количество столбцов таблицы = 3 + 3 = 6

A\/B

¬С

(A\/B) /\ ¬С

Пример 4. Определите истинность формулы: F = ((С \/В)  В) /\ (А /\ В) => В.

Построим таблицу истинности этой формулы.

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

Пример 5. Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z.

Дан фрагмент таблицы истинности выражения F:

Какое выражение соответствует F?

1) ¬X/\¬Y/\Z 2) ¬X\/¬Y\/Z 3) X\/Y\/¬Z 4) X\/Y\/Z

Решение (вариант 1, через таблицы истинности):

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

¬X

¬Y

¬Z

¬X/\¬Y/\Z

¬X\/¬Y\/Z

X\/Y\/¬Z

X\/Y\/Z

Очевидно, что значения заданной функции F совпадают со значениями выражения X\/Y\/¬Z. Следовательно, правильный ответ – 3.

Ответ: 3

Решение (Вариант 2):

Чтобы не строить таблицу истинности для каждого выражения, можно просто перепроверить предложенные ответы по заданной таблице истинности. Т.е. в каждую из четырех предложенных функций последовательно подставлять значения переменных X, Y и Z, из заданной таблицы истинности и вычислять значения логического выражения. Если значения вычисляемого выражения совпадут со значением F во всех трех строчках заданной таблицы, то это и есть искомое выражение.

Рассмотрим данный конкретный пример:

1) первое заданное выражение ¬X/\¬Y/\Z = 0 при X=0, Y=0, Z=0, что не соответствует первой строке таблицы;

2) второе заданное выражение ¬X\/¬Y\/Z = 1 при X=0, Y=0, Z=1, что не соответствует второй строке таблицы;

3) третье выражение X\/Y\/¬Z соответствует F при всех предложенных комбинациях X,Y и Z;

4) четвертое выражение X\/Y\/Z = 1 при X=0, Y=0, Z=1, что не соответствует второй строке таблицы.

Ответ: 3

Для самостоятельного выполнения

Построить таблицу истинности для выражения
1. F= (AVB) & (¬AV¬B)
2. XVY& ¬Z.
Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X,Y,Z. Дан фрагмент таблицы истинности выражения F:

Какое выражение соответствует F

¬X /\ ¬Y /\ Z
¬X V ¬Y V Z
X V Y V¬Z
X V Y V Z

Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X,Y,Z. Дан фрагмент таблицы истинности выражения F:

Какое выражение соответствует F?

¬X /\¬Y /\¬Z
X /\ Y /\ Z
X V Y V Z
¬ X V¬Y V¬Z

Контрольная работа по теме «Основы логики» 9 класс

ФИО________________________________________________________________________________

Контрольная работа_Логика_№1

В-1

Логическая операция с использованием связки «и», называется —

а) дизъюнкция;

б) инверсия;

в) конъюнкция

г) импликация

д) эквивалентность

Знаком «» обозначается —

а) инверсия;

б) конъюнкция;

в) эквивалентность

г) импликация

д) дизъюнкция;

Определите какой логической операции соответствует таблица истинности:

А	Результат
0	1
1	0

а) конъюнкция;

б) дизъюнкция;

в) импликация;

г) эквивалентность

д) инверсия

Постройте таблицу истинности для логической операции «эквивалентность»

А	В
0	0
0	1
1	0
1	1

Приведите 1 пример сложного высказывания, построенного с использованием логической операции «импликация»

__________________________________________________________________________________________________________________________

Запиши высказывания в виде логической формулы:

Если в кинотеатре идет неинтересный фильм или у меня нет денег, то я останусь дома.

Пришла весна, и растаял снег.

a___________________________b_________________________

Укажите порядок вычисления значения логического выражения: (К  Ā)  А → К

Сколько строк в таблице истинности для выражения: (К  Ā)  А → К

Сколько столбцов в таблице истинности для выражения: (К  Ā)  А → К

Постройте таблицу истинности выражения (К  Ā) → К

ФИО________________________________________________________________________________

Контрольная работа_Логика_№1

В-2

Логическая операция с использованием связки «или», называется —

а) инверсия;

б) дизъюнкция;

в) конъюнкция;

г) эквивалентность

д) импликация

Таким образом: «Ā» обозначается —

а) эквивалентность

б) конъюнкция;

в) импликация

г) дизъюнкция;

д) инверсия;

А	В	Результат
0	0	1
0	1	1
1	0	0
1	1	1

Определите какой логической операции соответствует таблица истинности:

а) конъюнкция;

б) дизъюнкция;

в) импликация;

г) эквивалентность

д) инверсия

Постройте таблицу истинности для логической операции «конъюнкция»

А	В	Результат
0	0
0	1
1	0
1	1

Приведите 1 пример сложного высказывания, построенного с использованием логической операции «эквивалентность»

__________________________________________________________________________________________________________________________

Запиши высказывание в виде логической формулы:

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

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

a___________________________b_________________________

Укажите порядок вычисления значения логического выражения: (Ā  С) ↔А  С

Сколько строк в таблице истинности для выражения: (Ā  С) ↔А  С

Сколько столбцов в таблице истинности для выражения: (Ā  С) ↔А  С

Постройте таблицу истинности выражения: Ā  (С→А)

ФИО________________________________________________________________________________

Контрольная работа_Логика_№1

В-3

Логическая операция с использованием связки «тогда и только тогда, когда…», называется —

а) инверсия;

б) конъюнкция;

в) дизъюнкция;

г) импликация

д) эквивалентность

Знаком «» обозначается —

а) инверсия;

б) конъюнкция;

в) дизъюнкция;

г) импликация

д) эквивалентность

А	В	Результат
0	0	0
0	1	1
1	0	1
1	1	1

Определите какой логической операции соответствует таблица истинности:

а) конъюнкция;

б) дизъюнкция;

в) импликация;

г) эквивалентность

д) инверсия

Постройте таблицу истинности для логической операции «импликация»

А	В
0	0
0	1
1	0
1	1

Приведите 1 пример сложного высказывания построенного, с использованием логической операции «инверсия»

______________________________________________________________________________________

_________________________________________________________________________________

Запиши высказывание в виде логической формулы:

Обычно вечером я иду на тренировку или гуляю с собакой.

Если в расписании на завтра нет первого уроа, то я высплюсь.

a___________________________b_________________________

Укажите порядок вычисления значения логического выражения: (К  А)  Ā → К

Сколько строк в таблице истинности для выражения: (К  А)  Ā → К

Сколько столбцов в таблице истинности для выражения: (К  А)  Ā → К

Постройте таблицу истинности выражения: (К  Ā) → К

ФИО________________________________________________________________________________Контрольная работа_Логика_№1

В-4

Логическая операция с использованием связки «если…, то…», называется —

а) импликация

б) конъюнкция;

в) дизъюнкция;

г) инверсия;

д) эквивалентность

Знаком «» обозначается —

а) эквивалентность

б) конъюнкция;

в) дизъюнкция;

г) импликация

д) инверсия;

А	В	Результат
0	0	0
0	1	0
1	0	0
1	1	1

Определите какой логической операции соответствует таблица истинности:

а) конъюнкция;

б) дизъюнкция;

в) импликация;

г) эквивалентность

д) инверсия

Постройте таблицу истинности для логической операции «инверсия»

А	Результат
0
1

Приведите 1 пример сложного высказывания, построенного с использованием логической операции «дизъюнкция»

__________________________________________________________________________________

Запиши высказывание в виде логической формулы:

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

Если с другом вышел в путь, то веселей дорога.

a___________________________b_________________________

Укажите порядок вычисления значения логического выражения: (А  С) ↔ Ā  С

Сколько строк в таблице истинности для выражения: (А  С) ↔ Ā  С

Сколько столбцов в таблице истинности для выражения: (А  С) ↔ Ā  С

Постройте таблицу истинности выражения: С ↔ Ā  С

ФИО________________________________________________________________________________Контрольная работа_Логика_№1

В-5

Логическая операция с использованием связки «не», называется —

а) инверсия;

б) конъюнкция;

в) дизъюнкция;

г) импликация

д) эквивалентность

Знаком «» обозначается —

а) инверсия;

б) конъюнкция;

в) дизъюнкция;

г) импликация

д) эквивалентность

А	В	Результат
0	0	1
0	1	0
1	0	0
1	1	1

Определите какой логической операции соответствует таблица истинности:

а) конъюнкция;

б) дизъюнкция;

в) импликация;

г) эквивалентность

д) инверсия

Постройте таблицу истинности для логической операции «дизъюнкции»

А	В
0	0
0	1
1	0
1	1

Приведите 1 пример сложного высказывания построенного, с использованием логической операции «конъюнкция»

____________________________________________________________________________________

___________________________________________________________________________________________

Запиши высказывание в виде логической формулы:

Сегодня я буду участвовать в кроссе и если пробегу дистанциюбыстрее всех, то получу медаль.

Прозвенел звонок, и все побежали на перемену.

a___________________________b_________________________

Укажите порядок вычисления значения логического выражения: (Ā  ) ↔А  С

Сколько строк в таблице истинности для выражения: (Ā  ) ↔А  С

Сколько столбцов в таблице истинности для выражения: (Ā  ) ↔А  С

Постройте таблицу истинности выражения: (Ā  )

Открытый урок на тему:»Логические операции» (10 класс) | Методическая разработка по информатике и икт (10 класс):

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

Класс: 10

Тип урока: урок изучения нового материала

Оборудование: приложение «Логические операции» (Приложение 1)

Планируемые результаты:

предметные — формирование представления о разделе математики — алгебре логики, высказывании как ее объекте, об операциях над высказываниями;

метапредметные — развитие навыков анализа логической структуры высказываний; понимание связи между логическими операциями и логическими связками, умение использовать знаково-символических средств, умение осуществлять итоговый и пошаговый контроль по результату выполнения заданий, умение формулировать свои затруднения.

личностные — понимание роли фундаментальных знаний как основы современных информационных технологий.

Формы работы учащихся: индивидуальная, групповая, фронтальная работа.

План урока:

1. Организационный момент 1 минут

2. Формулировка темы и целеполагание. 3 минуты

3. Изучение нового материала (логические операции) 10 минут

4. Закрепление материала, решение задач (практическая часть) 10 минут

5. Изучение нового материала (приоритет операций, алгоритм заполнения таблицы истинности) 2 минут

6.Закрепление, решение задач ЕГЭ 15 минут

7. Рефлексия, (три М), выставление оценок 4 минут

1. Организационный момент 1 минут

2. Формулировка темы и целеполагание. 3 минуты

Стадия «Вызов»

Актуализация ранее изученного материала:

– Вспомните, что такое алгебра логики? /Аппарат, который позволяет выполнять действия над высказываниями/
– Что такое высказывание? /Предложение, относительно которого имеет смысл говорить истинно оно или ложно/

Приём «Верные и неверные утверждения» (на партах бланки для ответов)

– Перед вами бланки:

1.	2.	3.	4.	5.	6.	7.	8.	9.	10.

– Я буду зачитывать утверждения. Вы должны поставить знак «+», если считаете, что утверждение верное, и знак «-», если считаете, что утверждение неверное.

Любое логическое выражение либо истинно, либо ложно.
Сложное логическое выражение содержит высказывания, объединенные какой-то одной логической операцией.
Истинность сложного высказывания можно определить, зная истинность или ложность входящих в него высказываний.
Результатом операции отрицания над высказыванием «Пушкин – не гениальный русский поэт» является высказывание «Пушкин – гениальный русский поэт».
Высказывание «4 – простое число» истинно. Высказывание «4 – не простое число» ложно.
Высказывание «Тигр – это полосатый зверь или домашнее животное», полученное при помощи логического сложения, истинно.
Высказывание «Январь – последний зимний месяц и в нем всегда 31 день», полученное при помощи логического умножения, истинно.
Высказывание «День сменяет ночь тогда и только тогда, когда солнце скрывается за горизонтом» получено при помощи операции логического равенства.
Высказывание «Если число Х делится на 3, то оно делится и на 9», образованное при помощи операции логического следования, является истинным.
Даны высказывания «Учитель должен быть умным» и «Учитель должен быть справедливым». Объединение этих высказываний при помощи логической операции конъюнкции означает, что учитель должен быть одновременно и умным, и справедливым.

– Что у вас получилось? Аргументируйте свой ответ (ситуация с противоречивыми мнениями обучающихся).
– Мы проверим правильность ваших мнений чуть позже. Отложите бланки в сторону.
– Определите тему урока, исходя из предложенных высказываний. /Логические операции/

3.Изучение нового материала (логические операции) 10 минут

Стадия «Осмысление»

Чтобы проверить правильность ваших ответов, запустите приложение «Логические операции» и ознакомьтесь с его содержанием.

– О каких логических операциях идет речь? /Инверсия, дизъюнкция, конъюнкция, импликация и эквивалентность/

Приём «Концептуальная таблица»

На доске таблица:

Линия сравнения	Логическая операция 1	Логическая операция 2	Логическая операция 3	Логическая операция 4	Логическая операция 5

– Выделите линии для сравнения перечисленных вами логических операций. (чем могут отличаться операции)

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

Линия сравнения	Инверсия	Конъюнкция	Дизъюнкция	Импликация	Эквивалентность
Название
Обозначение
Союз
Истинность результата операции
Таблица истинности

– Заполните Google таблицу, используя приложение «Логические операции», самостоятельно (работа в группах).

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

– Используя данные сводной таблицы, решите следующие задачи.

4. Закрепление материала, решение задач (практическая часть) 10 минут

Задача 1. Дан фрагмент таблицы истинности выражения F. Какое выражение соответствует F?

¬X ∧ ¬Y ∧ ¬Z
X ∧ Y ∧ Z
X ∨ Y ∨ Z
¬X ∨ ¬Y ∨ ¬Z

Задача 2. Заполните таблицы истинности в тесте по теме Логические операции «Алгебра логики» (библиотека МЭШ) Какие возникли затруднения?

Задача 3. Составьте таблицу истинности для выражения А∧¬В∧С∨ ¬А∧В∧С. В чем может быть затруднение при выполнении этого задания?

5. Изучение нового материала (приоритет операций, алгоритм заполнения таблицы истинности) 2 минуты

Работа с учебником стр 171-172

6.Закрепление, решение задач ЕГЭ 15 минут

Возвращаемся к задаче 3.

http://kpolyakov.spb.ru/school/probook/tests.htm тест 18. Таблицы истинности

глава 3. Онлайн-тесты для 10 класса

7. Рефлексия, выставление оценок 4 минут

Стадия «Рефлексия»

– Какова тема нашего урока? /Логические операции/

– О каких логических операциях вы узнали на уроке? /Инверсия, дизъюнкция, конъюнкция, импликация и эквивалентность/

– Дано высказывание «В библиотеке можно взять книгу или встретить знакомого». В результате какой операции было получено данное высказывание? /Дизъюнкция/

– Даны высказывания «Идёт дождь» и «На улице сыро». Какое высказывание получится, если применить логическую операцию импликация?/Если идет дождь, то на улице сыро/

– Определите истинность следующего высказывания «С помощью компьютера нельзя обработать информацию тогда и только тогда, когда он не включен (примечание: компьютер не включен)» /Истинно/

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

Правильно заполненный бланк:

1.	2.	3.	4.	5.	6.	7.	8.	9.	10.
+	—	+	+	—	+	—	+	—	+

А закончить наш урок мне хотелось бы словами Льюиса Кэрролла:

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

Листок контроля учени___ 10 класса _______________________________________________

Дополнительное задание на составление таблицы истинности

Составьте таблицу истинности для логического выражения (выполнить в тетради):

A → B ~ C & A V B

Количество баллов за тест ________

Оцените свою работу на уроке (выберите из второго столбца подходящее вам продолжение высказывания из первого столбца).

Закончите предложение:

На уроке мне было трудно ___ ________

___________________________________

Контрольная работа по информатике на тему: Алгебра логики. Таблицы истинности.

Просмотр содержимого документа
«Контрольная работа по информатике на тему: Алгебра логики. Таблицы истинности.»

Контрольная работа

по теме: Алгебра логики. Таблицы истинности

Выполнил ученик ______ класса _________________________________________«___»_____2021 г.

Вариант 1

Напишите ответ следующим утверждениям, с которыми вы согласны или нет.

(Ложь или Истина)

	Логическое умножение называется – конъюнкцией
	Логическое сложение называется – инверсией
	Логическое отрицание называется – дизъюнкцией
	Логическое сложение называется – дизъюнкцией
	Логическое отрицание называется – инверсией
	Логическое сложение называется – конъюнкцией

Для какой операции, высказывание, является истинным тогда и только тогда, когда оба исходных высказывания истинны?

1) конъюнкция

2) дизъюнкция

3) импликация

4) эквивалентность

5) инверсия

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

	Гранатовый сок полезен.	А	В
	Заниматься различными видами спорта вредно.
	Чистить зубы утром и вечером полезно.
	Сидеть за компьютером играя в игры целый день полезно.
	Свежий воздух не приносит пользы для человека.
	Сахар является сладким продуктом.
Напишите полученные ответы из задания № 1 для переменной А

логическими операндами.

Определите, для какой операции представлена таблица истинности:
дизъюнкция	0	0	1
импликация	0	1	1
конъюнкция	1	0	0
эквивалентность	1	1	1

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

	Отрицание
	Конъюнкция
	Действия в скобках
	Дизъюнкция
	Импликация
	Эквивалентность

Для высказывания построили таблицу истинности. Выберите верную.

1)	0	0	1	0	2)	0	0	0	1	3)	0	0	0	1
	0	1	0	0		0	1	0	1		0	1	1	0
	1	0	1	1		1	0	0	1		1	0	1	0
	1	1	0	0		1	1	1	0		1	1	1	0

Составьте таблицу истинности для логического выражения

Какое выражение F соответствует данному фрагменту таблицы истинности

X	Y	Z	F
1	0	1	1
1	1	0	0
1	1	1	0

2) 3)

Контрольная работа

по теме: Алгебра логики.

Таблицы истинности

Выполнил ученик ______ класса _________________________________________«___»_____2021 г.

Вариант 2

Напишите ответ следующим утверждениям, с которыми вы согласны или нет.

(Ложь или Истина)

	Логическое сложение называется – инверсией
	Логическое отрицание называется – инверсией
	Логическое отрицание называется – дизъюнкцией
	Логическое сложение называется – конъюнкцией
	Логическое сложение называется – дизъюнкцией
	Логическое умножение называется – конъюнкцией

Для какой операции, высказывание, является ложным тогда и только тогда, когда оба исходных высказывания ложны?

1) конъюнкция

2) дизъюнкция

3) импликация

4) эквивалентность

5) инверсия

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

	Апельсиновый сок не полезен.	А	В
	Заниматься различными видами танца вредно.
	Делать утром зарядку полезно.
	Смотреть целый день телевизор полезно.
	Свежий воздух приносит пользу для человека.
	Большое количество соли считается вредно для организма.
Напишите полученные ответы из задания № 1 для переменной А

логическими операндами.

Определите, для какой операции представлена таблица истинности:
дизъюнкция	0	0	1
импликация	0	1	0
конъюнкция	1	0	0
эквивалентность	1	1	1

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

	Эквивалентность
	Отрицание
	Действия в скобках
	Конъюнкция
	Дизъюнкция
	Импликация

Для высказывания построили таблицу истинности. Выберите верную.

1)	0	0	1	0	2)	0	0	0	1	3)	0	0	1	1
	0	1	0	0		0	1	0	1		0	1	1	1
	1	0	1	1		1	0	0	1		1	0	0	0
	1	1	0	0		1	1	1	0		1	1	0	1

Составьте таблицу истинности для логического выражения

Какое выражение F соответствует данному фрагменту таблицы истинности

X	Y	Z	F
0	0	1	0
0	1	0	0
0	1	1	1

2) 3)

L04: Комбинационная логика

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

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

Есть хорошие альтернативы, устраняющие недостатки упомянутое выше. Таблицы истинности представляют собой простую табличную представление, которое определяет значения выходов для каждого возможная комбинация цифровых входов.3 = 8 $ комбинаций трех входных значений, поэтому имеется 8 строк в таблице истинности. Это просто систематически перечислять 8 комбинаций, что упрощает чтобы гарантировать, что никакая комбинация не пропущена при построении Спецификация. А так как выходные значения указаны явно, нет места неверному истолкованию желаемый функционал!

Таблицы истинности

— отличный выбор для устройств с небольшим количество входов и выходов. К сожалению, они не совсем практично, когда у устройств много входов.{64} $ строк. Хм, не знаю как практично то есть! Если мы ввели правильное выходное значение для строки один раз в секунду, потребуется 584 миллиарда лет, чтобы заполнить Таблица!

Другая альтернативная спецификация — использовать булевы уравнения. чтобы описать, как вычислить выходные значения из входных значения с использованием булевой алгебры. Мы используем операции логические операции И, ИЛИ и XOR, каждая из которых требует двух Логические операнды и NOT, который принимает единственный логический операнд.Используя таблицы истинности, описывающие эти логические операции, легко вычислить выходное значение из конкретная комбинация входных значений с использованием последовательности операции, изложенные в уравнении.

Позвольте мне сказать несколько слов об обозначении, используемом для Boolean уравнения. Входные значения представлены именем вход, в этом примере один из A, B или C. Цифровой входное значение 0 эквивалентно логическому значению FALSE и значение цифрового входа 1 эквивалентно логическому значению ИСТИННЫЙ.

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

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

Логическая операция ИЛИ представлена сложением операция, всегда отображается как знак «+».

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

Таблицы истинности и булевы уравнения взаимозаменяемы. Если мы есть логическое уравнение для каждого выхода, мы можем заполнить столбцы вывода для строки таблицы истинности путем оценки Булевы уравнения, использующие конкретную комбинацию входных данных значения для этой строки.Например, чтобы определить значение Y в первой строке таблицы истинности мы заменим Логическое значение FALSE для символов A, B и C в уравнении а затем используйте булеву алгебру для вычисления результата.

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

Начните с просмотра таблицы истинности и ответа на вопрос. «Когда Y имеет значение 1?» Или на языке булевой алгебры: «Когда Y ИСТИНА?» Ну, Y ИСТИНА, когда входные данные соответствуют строке 2 таблицы истинности, ИЛИ в ряд 4, ИЛИ в ряды 7 ИЛИ 8.Всего 4 комбинации входов, для которых Y — ИСТИНА. Соответствующие Таким образом, логическое уравнение представляет собой ИЛИ для четырех членов, где каждый член является логическим выражением, которое принимает значение ИСТИНА для определенного комбинация входов.

Строка 2 таблицы истинности соответствует C = 0, B = 0 и A = 1. В соответствующее логическое выражение: $ \ overline {C} \ cdot \ overline {B} \ cdot A $, выражение, которое оценивается как ИСТИНА тогда и только тогда, когда C равно 0, B равно 0, а A — 1.

Логическое выражение, соответствующее строке 4, — $ \ overline {C} \ cdot B \ cdot A $.И так далее для строк 7 и 8.

Этот подход всегда дает нам выражение в виде сумма произведений. «Сумма» относится к операциям ИЛИ и «Продукты» относятся к группам операций И. В этом Например, у нас есть сумма четырех терминов продукта.

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

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

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

Логический элемент И выводит 1 тогда и только тогда, когда на входе A 1 и вход B равен 1, отсюда и название AND. Библиотека будет обычно включают логические элементы И с 3 входами, 4 входами и т. д., который производят 1 выход тогда и только тогда, когда все их входы 1.

Логический элемент ИЛИ выводит 1, если вход A равен 1 * или *, если вход B равно 1, отсюда и название OR. Опять же, библиотека обычно включить логические элементы ИЛИ с 3 входами, 4 входами и т. д., которые производят 1 выход, когда хотя бы один из их входов 1.

Это стандартные условные обозначения для вентилей И и ИЛИ. Обратите внимание, что символ И находится прямо на стороне ввода, в то время как символ ИЛИ изогнут. Немного попрактиковавшись, вы легко запомнить, какие условные обозначения какие.

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

Структура схемы в точности повторяет структуру булево уравнение. Мы используем инверторы для выполнения необходимых Логические операции НЕ. В уравнении суммы произведений инверторы работают на определенных входных значениях, в этом случае A, B и C. Чтобы схема была удобна для чтения, мы использовали отдельный инвертор для каждой из четырех операций НЕ в Логическое уравнение, но в реальной жизни мы можем инвертировать вход C один раз, чтобы произвести сигнал NOT-C, затем использовать этот сигнал всякий раз, когда Необходимо значение NOT-C.

Каждый из четырех терминов продукта построен с использованием 3-входного И ворота. И термины продукта объединяются по ИЛИ с использованием 4-входного ИЛИ ворота. Последняя схема имеет слой инверторов, слой И ворота и последние ворота ИЛИ. В следующем разделе мы поговорить о том, как построить логические элементы И или ИЛИ с множеством входных данных из компоненты библиотеки с меньшим количеством входов.

Задержка распространения для схемы суммы произведений выглядит довольно короткий: самый длинный путь от входов к выходам включает инвертор, логический элемент И и логический элемент ИЛИ.Мы действительно можем реализовать любое логическое уравнение в схеме с $ t _ {\ textrm {PD}} $ из трех задержек гейта?

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

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

В нашем списке дел из предыдущего раздела мы выясняем, как построить логические элементы И и ИЛИ с множеством входов. Это будет необходимо при создании схемных реализаций с использованием уравнение суммы продуктов в качестве нашего шаблона. Предположим в нашей библиотеке ворот есть только ворота с 2 входами, и мы знаем, как построить более широкие ворота, использующие 2-входные ворота в качестве строительных блоков. Мы будем работать над созданием вентилей с 3 и 4 входами, но подход, который мы используем, можно обобщить для создания логических элементов И и ИЛИ любой желаемой ширины.

Подход, показанный здесь, основан на ассоциативном свойстве оператор И. Это означает, что мы можем выполнить N-образное И с помощью выполнение парных операций И в любом удобном порядке. Операции OR и XOR операции также ассоциативны, поэтому будет работать тот же подход для разработки широких схем OR и XOR из соответствующих 2-х входной вентиль. Просто замените логические элементы ИЛИ с двумя входами или ИЛИ с двумя входами. ворота для 2-входных элементов И, показанных ниже, и вы хорошо пойти!

Давайте начнем с разработки схемы, которая вычисляет AND трех входов A, B и C.В показанной здесь схеме мы сначала вычислить (A AND B), затем AND, чтобы получить результат C.

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

Мы также можем связать четыре входа по-другому: вычисление (A AND B) параллельно с (C AND D), затем объединение эти два результата с использованием третьего логического элемента И. Используя этот подход, мы строим дерево ворот И.

Какой подход лучше: цепи или деревья? Сначала мы должны решить, что мы подразумеваем под словом «лучший». При проектировании цепей, нас интересует стоимость, которая зависит от количество компонентов и производительность, которую мы характеризуем задержка распространения цепи.

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

Цепная схема в середине имеет $ t _ {\ textrm {PD}} $, равное 3. задержки ворот, и мы видим, что $ t _ {\ textrm {PD}} $ для Цепочка N-входов будет иметь задержки затвора N-1. Задержка распространения цепочки линейно растут с количеством входов.

Схема дерева внизу имеет $ t _ {\ textrm {PD}} $, равное 2 ворота, меньше цепи. Задержка распространения деревьев логарифмически растет с количеством входов. Конкретно, задержка распространения древовидных схем, построенных с использованием вентилей с 2 входами растет как log2 (N).Когда N велико, древовидные схемы могут иметь значительно лучшая задержка распространения, чем в цепных схемах.

Задержка распространения — это верхняя граница задержки в наихудшем случае. от входов к выходам и является хорошим показателем производительности предполагая, что все входные данные поступают одновременно. Но в целом цепи, A, B, C и D могут прибыть в разное время в зависимости от $ t _ {\ textrm {PD}} $ схемы, генерирующей каждый. Предположим, что вход D поступает значительно позже другого. входы.Если бы мы использовали древовидную схему для вычисления И всех четыре входа, дополнительная задержка при вычислении Z составляет два элемента задержки после прибытия D. Однако, если мы воспользуемся цепочкой схемы, дополнительная задержка в вычислении Z может быть столь же малой как одна задержка ворот.

Мораль этой истории: трудно понять, что реализация подсхемы, как показано здесь 4-входное И, даст наименьшее общее значение $ t _ {\ textrm {PD}} $, если мы не знаем $ t _ {\ textrm {PD}} $ схем, которые вычисляют значения для входных сигналов.

При разработке схем КМОП отдельные вентили естественно инвертирование, поэтому вместо использования логических элементов AND и OR, в лучшем случае производительность, которую мы хотим использовать, показанные вентили NAND и NOR здесь. Логические элементы NAND и NOR могут быть реализованы как одна CMOS вентиль, включающий одну схему подтягивания и одну схему подтягивания. И и логическим элементам ИЛИ требуются два элемента КМОП в их реализация, например , логический элемент NAND, за которым следует ИНВЕРТОР. Мы поговорим о том, как построить сумму произведений. схемы с использованием NAND и NOR в следующем разделе.

Обратите внимание, что операции NAND и NOR не ассоциативны: И-НЕ (A, B, C) не равно NAND (NAND (A, B), C). Итак, мы невозможно построить логический элемент NAND с множеством входов, создавая дерево NAND с 2 входами. Мы поговорим об этом в следующем раздел тоже!

Мы упоминали операцию «исключающее ИЛИ», иногда вызывал XOR несколько раз. Эта логическая функция очень полезна при построении схем для арифметических вычислений или расчетов по четности. Как вы увидите в лабораторной работе 2, реализация логического элемента XOR с двумя входами потребуется гораздо больше NFET и PFET, чем требуется для 2-входного ИЛИ ИЛИ НЕ.

Мы знаем, что можем придумать выражение суммы произведений для любую таблицу истинности и, следовательно, построить реализацию схемы, используя ИНВЕРТОРЫ, И ворота, ИЛИ ворота. Оказывается, мы можем построить схемы с той же функциональностью, использующие только 2-INPUT NAND ворота — мы говорим, что 2-INPUT NAND — это универсальные ворота.

Здесь мы показываем, как реализовать построение суммы произведений блоки, использующие только 2-входные вентили NAND. Через минуту мы показать более прямую реализацию для суммы продуктов с использованием только NAND, но эти маленькие схемы являются доказательством правильности концепции. показывая, что существуют эквивалентные схемы только для NAND.

2-INPUT NOR ворота также универсальны, как показывают эти маленькие схемы.

Логика инвертирования требует некоторого привыкания, но это ключ к разработке недорогих высокопроизводительных схем в CMOS.

Сейчас самое подходящее время, чтобы взглянуть на документацию к библиотеке логических вентилей, которую мы будем использовать для наши проекты — ищите раздаточный материал The Standard Cell Library . Информация на этом слайде взята оттуда.

В библиотеке есть оба инвертирующих затвора (например, инверторы, NAND и NOR) и неинвертирующие вентили (такие как буферы, AND и ИЛИ).Зачем включать оба типа ворот? Не сделал мы просто узнаем, что можем построить любую схему, используя только NAND или НИ?

Хорошие вопросы! Мы получим некоторое представление об ответах, если мы посмотрите на эти три реализации для 4-входного И функция.

Верхняя схема представляет собой прямую реализацию с использованием 4 входов. И ворота доступны в библиотеке. $ T _ {\ textrm {PD}} $ из строб составляет 160 пикосекунд, а его размер составляет 20 квадратных микрон. Не беспокойтесь о фактических цифрах, что на этом слайде важно то, как сравниваются числа между конструкции.

Средняя схема выполняет ту же функцию, на этот раз используя вентиль NAND с 4 входами, подключенный к инвертору, чтобы произвести И функциональность, которую мы хотим. $ T _ {\ textrm {PD}} $ этого цепь составляет 90 пикосекунд, что значительно быстрее, чем одиночная ворота выше. Компромисс в том, что размер несколько больше.

Как такое может быть? Тем более что мы знаем вентиль И реализация — пара NAND / INVERTER, показанная посередине схема. Ответ в том, что создатели библиотеки решили сделать неинвертирующие ворота маленькими, но медленными, используя полевые МОП-транзисторы с гораздо меньшей шириной, чем используется в инвертирующих логических вентилях, которые были разработаны, чтобы быть быстрыми.

Зачем нам вообще использовать медленные ворота? Помните, что задержка распространения цепи задается самым длинным путем в сроки задержки от входов к выходам. В сложной схеме, есть много путей ввода / вывода, но это только компоненты на самом длинном пути, которые должны быть быстрыми, чтобы достичь наилучшего возможного общего значения $ t _ {\ textrm {PD}} $. В компоненты на других, более коротких путях, потенциально могут быть немного помедленнее. И компоненты на коротких путях ввода / вывода могут быть действительно очень медленно.Итак, для частей схемы, которые не чувствительны к скорости, это хороший компромисс для использования более медленные, но меньшие ворота. Общая производительность не пострадали, но общий размер улучшился.

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

Инвертирующие вентили с 4 входами также разработаны с учетом этого компромисс в виду.Для максимальной производительности мы хотим используйте древовидную схему 2-входных вентилей, как показано в нижнем схема. Эта реализация сокращает время на 10 пикосекунд. $ t _ {\ textrm {PD}} $, но стоит нам немного больше по размеру.

Присмотритесь к нижнему контуру. Эта схема дерева использует два логических элемента И-НЕ, выходы которых объединены с вентилем ИЛИ-НЕ. Действительно ли это вычисляет AND для A, B, C и D? Ага, как ты можно проверить, построив таблицу истинности для этого комбинационного система, использующая таблицы истинности для NAND и NOR.

Эта схема является хорошим примером применения особая логическая идентичность, известная как закон Деморгана. Есть две формы закона Деморгана, обе из которых показано здесь. Верхняя форма — это та, которая нас интересует для анализа нижнего контура. Это говорит нам, что НИ А with B эквивалентно AND для (NOT A) с (NOT B). Так что Логический элемент ИЛИ-НЕ с 2 входами можно рассматривать как логический элемент И с 2 входами с инвертирующие входы. Как это помогает? Теперь мы видим, что нижний контур на самом деле является деревом логических элементов И, где инвертирующие выходы первого слоя совпадают с инвертирующими входы второго слоя.

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

Используя закон Деморгана, мы можем ответить на вопрос, как создавать NAND и NOR с большим количеством входов. Наши ворота Библиотека включает инвертирующие вентили до 4 входов. Зачем останавливаться там? Ну, в цепочке выпадающего списка 4-входного логического элемента И-НЕ 4 NFET включены последовательно, а сопротивление проводящих каналов составляет начинаю складывать.Мы могли бы сделать NFET шире, чтобы компенсировать, но тогда ворота становятся намного больше и шире NFET-транзисторы создают более высокую емкостную нагрузку на входные сигналы. В количество возможных компромиссов между размером и скоростью растет быстро с количеством входов, поэтому обычно разработчику библиотеки лучше всего остановиться на воротах с 4 входами и позволить схемотехник берет это оттуда.

К счастью, закон Деморгана показывает нам, как строить деревья из чередование NAND и NOR для построения инвертирующей логики с большим количество входов.Здесь мы видим схему для 8-входной NAND и вентиль ИЛИ-НЕ с 8 входами.

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

Точно так же подумайте о среднем слое вентилей NAND справа. схему как логические элементы ИЛИ с инвертирующими входами и видим, что мы действительно есть дерево логических элементов ИЛИ с инвертирующим выходом.

Теперь давайте посмотрим, как построить схемы суммы произведений, используя инвертирующая логика.Две показанные здесь схемы реализуют один и тот же логическая функция суммы произведений. Тот, что наверху, использует два слои NAND-ворот, один внизу, два слоя NOR ворота.

Давайте визуализируем закон Деморгана в действии наверху схема. Логический элемент И-НЕ с Y на выходе может быть преобразован по закону Деморгана в логический элемент ИЛИ с инвертирующими входами. Итак, мы можем перерисовать схему в левом верхнем углу как схему показано вверху справа. Теперь обратите внимание, что инвертирующие выходы первого слоя отменяются инвертирующими входами второй слой, шаг, который мы можем показать визуально, удалив соответствующие инверсии.И, вуаля, мы видим схему NAND / NAND в форме суммы продуктов: слой инверторов, слой AND ворота и ворота ИЛИ, чтобы объединить термины продукта.

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

Глядя на схему NOR / NOR в левом нижнем углу, мы видим ее имеет 4 инвертора, тогда как схема NAND / NAND имеет только один.Зачем нам вообще использовать реализацию NOR / NOR? Это нужно сделать с загрузкой на входах. В верхней цепи вход A подключается в общей сложности к четырем переключателям MOSFET. В нижней цепи, он подключается только к двум переключателям MOSFET в инвертор. Итак, нижняя схема накладывает половину емкостной нагрузка на сигнал A. Это может быть значительным, если сигнал A подключен ко многим таким цепям.

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

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

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

Вот уравнение из начала этой главы, включает 4 товарных термина. Мы будем использовать вариант идентификация редукции, включающая логическое выражение альфа и единственная переменная A. Если посмотреть на термины продукта, средние две предлагаем возможность применить тождество сокращения, если мы позволим альфа — выражение (C AND B).Итак, мы упрощаем середину два термина продукта должны быть только альфа, , то есть , (C AND B), исключив переменную A из этой части выражения.

Рассматривая теперь три термина продукта, мы видим, что первый и последние термины также могут быть сокращены, на этот раз позволяя альфе быть выражение (НЕ C и A). Вау, это эквивалентное уравнение значительно меньше! Считая инверсии и попарные операции, исходное уравнение имеет 14 операций, а упрощенное уравнение имеет 4 операции.Упрощенная схема была бы намного дешевле в сборке и имеет меньший размер $ t _ {\ textrm {PD}} $ в торговаться!

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

Еще один способ подумать об упрощении — поискать таблица истинности для ситуаций безразличия. Например, посмотрите на первую и третью строки исходной таблицы истинности на слева. В обоих случаях A равно 0, C равно 0, а выход Y равен 0. Единственная разница — это значение B, которое, как мы можем определить, равно не имеет значения, когда и A, и C равны 0. Это дает нам первую строку таблицы истинности справа, где мы используем X, чтобы указать, что значение B не имеет значения, когда A и C оба равны 0.По сравнивая строки с одинаковым значением Y, мы можем найти другие безразличные ситуации.

В таблице истинности с безразличием всего три строки. где результат равен 1. И, по сути, последняя строка является избыточной. в том смысле, что совпадающие входные комбинации (011 и 111) закрыты вторым и четвертым рядами.

Термины продукта, полученные из второй и четвертой строк, в точности соответствуют условия продукта, которые мы нашли, применив сокращение личность.

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

Здесь показана упрощенная схема. Посмотрим, как он работает, когда A равно 1, B равно 1, а C выполняет переход от 1 до 0. Перед переходом C равно 1, и мы можем видеть из аннотированные значения узла, что это нижний логический элемент И что приводит к выходу Y равным 1.

Когда C переходит в 0, нижний логический элемент AND выключается и верхний вентиль И включается, и, в конце концов, выход Y становится 1 опять таки. Но включение верха И задерживается из-за $ t _ {\ textrm {PD}} $ инвертора, поэтому кратко период времени, когда ни один логический элемент И не включен, а выход на мгновение становится 0.Эта короткая отметка в значении Y называется сбой, и это может привести к краткосрочным изменениям на многих значения узла по мере его распространения через другие части схемы. Все эти изменения потребляют электроэнергию, поэтому было бы хорошо избежать вот такие глюки, если можно.

Если мы включим в нашу реализацию третий термин продукта BA, схема по-прежнему вычисляет тот же долгосрочный ответ, что и раньше. Но теперь, когда A и B оба высоки, выход Y будет 1 независимо от значения входа C.Итак, 1 к 0 переход на входе C не вызывает сбоев на входе Y выход. Если вы вспомните последний раздел предыдущей главы, фраза, которую мы использовали для описания таких цепей, — lenient .

При попытке минимизировать выражение суммы произведений с помощью сокращение идентичности, наша цель — найти два термина продукта, которые можно записать как один меньший член продукта, исключив безразличная переменная. Это легко сделать, когда два термины продукта взяты из соседних строк в таблице истинности.Для Например, посмотрите на две нижние строки в этой таблице истинности. С выход Y равен 1 в обоих случаях, обе строки будут представлены в выражении суммы произведений для этой функции. Его легко заметить переменную безразличия: когда C и B оба 1, значение A не требуется для определения значения of Y. Таким образом, последние две строки таблицы истинности могут быть представлен одним термином продукта (B AND C).

Найти эти возможности было бы проще, если бы мы реорганизовали таблица истинности, чтобы соответствующие условия продукта были на соседние ряды.Вот что мы сделали в Карта Карно, сокращенно K-карта, показана справа. K-карта организует таблицу истинности как двумерную таблицу с ее строки и столбцы, помеченные возможными значениями для входы. На этой K-карте первая строка содержит записи о том, когда C равно 0, а вторая строка содержит записи, когда C равно 1. Точно так же первый столбец содержит записи для случаев, когда A равно 0 и B равно 0. И так далее. Записи в K-карте — это в точности так же, как записи в таблице истинности, они просто отформатировал иначе.

Обратите внимание, что столбцы перечислены в особой последовательности. это отличается от обычной двоичной последовательности счета. В этой последовательности, называемой кодом Грея, соседние метки отличаются ровно одна из их частей. Другими словами, для любых двух соседних столбцы, либо значение метки A изменилось, либо значение метки B.

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

Нотацию K-карты легко расширить до таблиц истинности. для функций с 4 входами, как показано здесь. Мы использовали Последовательность кода Грея как для строк, так и для столбцов. В виде раньше крайний левый и крайний правый столбцы смежны, как и верхний и нижний ряды.Опять же, когда мы переходим к соседнему столбец или соседняя строка, только одна из четырех меток ввода изменится.

Чтобы построить K-карту для функций от 6 переменных, нам понадобится Матрица значений 4х4х4. Это сложно нарисовать в 2D страницы, и было бы сложно определить, какие ячейки в 3D матрицы были смежными. Для более чем 6 переменных нам понадобится дополнительные габариты. Что-то, с чем мы можем справиться с компьютерами, но трудно тем из нас, кто живет только в трехмерном пространство!

На практике K-карты хорошо работают до 4 переменных, и мы будем придерживаться этого.Но имейте в виду, что вы можете обобщить технику K-карты на более высокие измерения.

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

Давайте представим понятие импликанта, причудливого имени. для прямоугольной области K-карты, где все элементы 1’s. Помните, что если введена 1, нам понадобится выражение суммы продуктов, которое нужно оценить как ИСТИНА для этого конкретная комбинация входных значений.

Мы требуем, чтобы ширина и длина импликанта были из 2, , то есть , область должна иметь 1, 2 или 4 строки и 1, 2 или 4 столбца.

Это нормально, когда импликанты накладываются друг на друга. Мы говорим, что импликант — это первичный импликант , если он не полностью содержится в любом другом импликанте. Каждый термин продукта в нашем окончательное минимизированное выражение суммы произведений будет связано с некоторая простая импликанта в K-отображении.

Давайте посмотрим, как эти правила работают на практике, используя эти два примера K-карт.Когда мы определяем основные импликанты, обведем их красным. Начиная с K-карты на слева первая импликанта содержит одноэлементную 1-ячейку не примыкает ни к какой другой ячейке, содержащей 1’s.

Второй простой импликант — это пара смежных единиц в верхний правый угол K-карты. Этот импликант имеет одна строка и два столбца, отвечающие нашим ограничениям на неявные размеры.

Нахождение простых импликант в правой K-карте немного сложнее.Напоминая, что левый и правый столбцы рядом, мы можем обнаружить простой импликант 2×2. Обратите внимание, что это простая импликанта содержит много меньших 1×2, 2×1 и 1×1 импликанты, но ни один из них не будет первостепенным, поскольку они полностью содержатся в импликанте 2×2.

Заманчиво нарисовать импликант 1×1 вокруг оставшихся 1, но на самом деле мы хотим найти самый большой импликант, который содержит именно эту ячейку. В данном случае это Здесь показан простой импликант 1×2.Почему мы хотим найти наибольшие возможные основные импликанты? Мы ответим на это вопрос через минуту …

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

Первый импликант, обведенный нами в кружок, соответствует термину продукта. $ \ overline {A} \ cdot \ overline {B} \ cdot C $, выражение, которое принимает значение ИСТИНА, когда A равно 0, B равно 0 и C равно 1.

Как насчет импликанта 1×2 в верхнем правом углу? Мы не хочу включать входные переменные, которые меняются по мере того, как мы двигаться в импликанте. В этом случае два входных значения постоянными остаются C (имеющее значение 0) и A (которое имеет значение 1), поэтому соответствующий член продукта $ A \ cdot \ overline {C} $.

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

Давайте попробуем другой пример. Помните, что мы ищем самые большие возможные основные импликанты. Хороший путь Чтобы продолжить, нужно найти некоторую не обведенную цифру 1, а затем определить самый крупный импликант, который мы можем найти, который включает эту клетку.

Есть импликант 2×4, который покрывает два средних ряда стола. Глядя на единицы в верхнем ряду, мы можем идентифицировать две импликанты 2×2, которые включают эти клетки.

Правый столбец покрывает импликант 4×1, оставив одинокую 1 в нижнем левом углу таблицы. Искать соседние единицы и запоминать таблицу — это циклический, мы можем найти импликант 2×2, включающий этот последний не обведен 1.

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

Теперь, когда мы определили основные импликанты, мы готовы построить минимальную сумму продуктов выражение.

Вот два примера K-карт, где мы показали только главные импликанты должны были покрыть все единицы на карте. Это означает, например, что в карте с 4 переменными мы не включал импликант 4×1, покрывающий правую столбец. Этот импликант был главным импликантом, поскольку он не был полностью ограничен каким-либо другим импликантом, но это не нужно было прикрывать всех, кто в Таблица.

Взглянув на верхний стол, мы соберем минимальный выражение суммы продуктов путем включения условий продукта для каждая из показанных импликантов. Верхний импликант имеет продукт термин А И (не С), а нижний импликант имеет произведение термин (B И C). Готово! Почему в результате уравнение минимальное? Если было еще какое-то сокращение, можно было бы применить, чтобы произвести еще меньший термин продукта, который будет означать, что существует более крупный импликант, который может иметь был обведен кружком на K-карте.

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

И мы закончили. Нахождение простых импликант в K-отображении — это быстрее и менее подвержено ошибкам, чем дурачиться с Boolean алгебраические тождества.

Обратите внимание, что выражение минимальной суммы произведений не обязательно уникальный. Если бы мы использовали другое сочетание простых чисел при создании нашего прикрытия мы бы придумали различное выражение суммы произведений.Конечно, двое выражения эквивалентны в том смысле, что они производят одинаковое значение Y для любой конкретной комбинации входных значений — в конце концов, они были построены из одной и той же таблицы истинности. И два выражения будут иметь одинаковое количество операции.

Итак, когда вам нужно придумать минимальную сумму продуктов выражение для функций до 4 переменных, K-карты — это путь идти!

Мы также можем использовать K-карты, чтобы помочь нам удалить глюки из вывода сигналы.Ранее в этой главе мы видели эту схему и заметил, что когда A было 1, а B было 1, то переход от 1 к 0 на C может вызвать сбой на выходе Y, так как нижний термин продукта отключен, а термин верхнего продукта включен.

Эта конкретная ситуация обозначена желтой стрелкой на K-карта, на которой мы переходим от ячейки на нижний ряд столбца 1–1 в ячейку верхнего ряда. Легко видеть, что мы оставляем одну неявную и переезжаем в другой.Это разрыв между двумя импликанты, которые приводят к потенциальному сбою на Y.

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

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

Таблица истинности, которую мы использовали в качестве примера, описывает очень полезное комбинационное устройство, называемое мультиплексором 2-к-1. Мультиплексор, или для краткости MUX, выбирает один из двух своих входов. значения в качестве выходного значения. Когда выбран вход, отмеченный S на диаграмме равно 0, значение на входе данных D0 становится значение выхода Y.K $ входных данных. Например, вот 4 к 1 мультиплексор с 4 входами данных и 2 входами выбора.

Мультиплексоры большего размера могут быть построены из дерева мультиплексоров 2 к 1, как показано на рисунке. здесь.

Чем интересны мультиплексоры? Один ответ заключается в том, что они предоставляют очень элегантный и общий способ реализации логической функции. Рассмотрим мультиплексор 8-к-1, показанный справа. 3 входа — A, B и CIN — используются в качестве трех сигналов выбора для MUX. Думайте о трех входах как о 3-битном двоичном номер.Например, когда все они равны 0, MUX будет выберите вход данных 0, и когда все они будут равны 1, MUX будет выберите ввод данных 7 и так далее.

Как упростить реализацию логической функции, показанной на таблица истинности? Что ж, подключим входы данных MUX к постоянным значениям, показанным в выходном столбце в таблица истинности. Значения на входах A, B и CIN вызовут MUX, чтобы выбрать соответствующую константу на входах данных как значение для выхода COUT.

Если позже мы изменим таблицу истинности, нам не придется перепроектировать сложную схему суммы произведений, мы просто необходимо изменить константы на входах данных. Подумайте о MUX как устройство поиска по таблице, которое можно перепрограммировать на реализовать в этом случае любое уравнение с тремя входами. Такого рода схема может использоваться для создания различных форм программируемых логика, где функциональность интегральной схемы не определено при изготовлении, но установлено во время этапа программирования, выполняемого пользователем позже время.N $ данных входы. Они полезны для N до 5 или 6, но для функции с большим количеством входов, экспоненциальный рост в цепи размер делает их непрактичными.

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

Даже XOR просто реализовать с одним мультиплексором 2 к 1!

Вот окончательная стратегия реализации логики с использованием доступные только для чтения.K $ выходных данных. Только один из выходные данные будут 1 (или ВЫСОКОЕ) в любой момент времени, что один определяется значением на выбранных входах. Jth выход будет 1, когда выбранные строки установлены в двоичном формате представление J.

Вот реализация памяти только для чтения для 2-выходного таблица истинности показана слева. Это конкретное устройство с двумя выходами это полный сумматор, который дополнительно используется как строительный блок схемы.

Три входа функции (A, B и CI) подключены к выбранным строкам декодера от 3 до 8.8 выходов декодер работает горизонтально на принципиальной схеме, и каждый помечены входными значениями, для которых этот выход будет ВЫСОКАЯ. Таким образом, когда входы равны 000, выход верхнего декодера будет быть ВЫСОКИМ, а все остальные декодеры выводят НИЗКИЙ. Когда входы 001 — , то есть , когда A и B равны 0, а CI — 1 — выход второго декодера будет ВЫСОКИМ. И так далее.

Выходы декодера управляют матрицей понижающих переключателей NFET. В матрице есть один вертикальный столбец для каждого вывода истины. Таблица.Каждый переключатель соединяет определенный вертикальный столбец с заземление, переводя его в НИЗКОЕ значение, когда переключатель включен. В Схема колонки спроектирована таким образом, что, если нет понижающих переключателей установите его значение на 0, его значение будет 1. Значение на каждом вертикальных столбцов инвертируется для получения окончательного результата значения.

Итак, как нам использовать всю эту схему для реализации функции описывается таблицей истинности? Для любой конкретной комбинации входные значения, ровно один из выходов декодера будет ВЫСОКИМ, все остальные будут низкими.Думайте о выходах декодера как о указание, какая строка таблицы истинности была выбрана входные значения. Все переключатели опускания, управляемые Будет включен выход декодера HIGH, заставляя вертикальный столбец, к которому они подключены LOW.

Например, если входы 001, выход декодера помечен 001 будет ВЫСОКИМ. Это включит выпадающий список в кружке переключатель, заставляя вертикальный столбец S НИЗКОЕ. Вертикаль COUT Колонка не опущена, поэтому она будет ВЫСОКОЙ.После вывода инверторы, S будет 1, а COUT будет 0, желаемый выход значения.

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

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

ПЗУ только для чтения, сокращенно ПЗУ, являются реализацией стратегия, которая игнорирует структуру конкретного логического выражение, которое будет реализовано. Размер ПЗУ и общий Макет определяется только количеством входов и выходов. Обычно матрица переключателей заполнена полностью, со всеми возможные места переключения заполнены раскрывающимся полевым транзистором. А отдельная операция физического или электрического программирования определяет какие переключатели фактически управляются линиями декодера.N $ строк и M выходных столбцов, точно соответствующих к размеру таблицы истинности.

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

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

Реализации схем MUX и ROM

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

Столбец с характеристиками

из AMS

Отправлено в июне 2005 г.

Топологически точные диаграммы существуют для одного, двух или трех операторов, но не для четырех или более операторов …

Тони Филлипс
Университет Стоуни-Брук,
тони по математике.sunysb.edu

Введение: Исчисление логических функций

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

Диаграмма Венна представляет собой графический способ иллюстрации исчисления логических функций. Это функции, которые присваивают утверждению значение истинности: 0 («ложь») или 1 («истина»). Рассчитывается, как эти функции сочетаются с основными операциями и, или нет, если они определены в

A и B истинны, если и A, и B истинны, и ложны в противном случае.
A или B истинно, если истинно либо A, либо B (или оба). Эквивалентно A или B ложны, если и A, и B ложны, и истинно в противном случае.
not A истинно, если A ложно, и false, если A истинно.

Значит, значение и, или и не соответствует обычному значению слов, за исключением того, что или означает «или» не в смысле «ты идешь или уходишь?» но в смысле «Вы, должно быть, заблуждаетесь или дезинформированы», где возможность того и другого не исключена.

Таблицы истинности

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

Утверждение not (A или (B and not C)) = not A и (не B или C) является «тавтологией» (т.е. значения левой и правой частей равны для любой комбинации значений A, B, C). Один из алгоритмических способов проверки того, что у нас действительно есть тавтология, состоит в использовании таблиц истинности: Табулируйте значение истинности левой части для всех возможных комбинаций значений истинности A, B, C (имеется 2 x 2 x 2 = 8 из них), сделайте то же самое для правой стороны и убедитесь, что выходы всегда одинаковы.

Левая сторона получается как

А	В	С	не C	B и не C	A или (B а не C)	нет (A или (B а не С))
0	0	0	1	0	0	1
0	0	1	0	0	0	1
0	1	0	1	1	1	0
0	1	1	0	0	0	1
1	0	0	1	0	1	0
1	0	1	0	0	1	0
1	1	0	1	1	1	0
1	1	1	0	0	1	0

, а правая сторона —

А	В	С	не B	не B или C	не	не А, а (не B или C)
0	0	0	1	1	1	1
0	0	1	1	1	1	1
0	1	0	0	0	1	0
0	1	1	0	1	1	1
1	0	0	1	1	0	0
1	0	1	1	1	0	0
1	1	0	0	0	0	0
1	1	1	0	1	0	0

и поскольку два последних столбца совпадают, эти два оператора эквивалентны.

Таблицы истинности и диаграммы

Существует графический способ интерпретации таблиц истинности, основанный на параллелизме между and, or, and not, и операциями пересечение, объединение, и , дополняющее в теории множеств. Параллелизм встроен в определения теоретико-множественных операций, поскольку X пересекаются, Y — это множество элементов, которые принадлежат X и Y, X union Y — множество элементов, которые принадлежат X или Y , а дополнение X — это набор элементов, которые не принадлежат X.

Для логических целей мы можем идентифицировать утверждение A с набором экземпляров, в которых A истинно; тогда логические операции над операторами — это в точности теоретико-множественные операции над соответствующими множествами. Идея диаграммы Венна состоит в том, чтобы представить множества фигурами на плоскости и рассуждать таким образом.

Чтобы повторить предыдущий пример в этом новом формате, мы представляем набор, соответствующий оператору A, набором точек внутри (синего) круга, а также для B (желтый) и C (красный), и мы размещаем эти круги так, чтобы произошли все возможные пересечения.Три круга находятся внутри прямоугольника, который представляет вселенную или набор всех возможных экземпляров, так что область за пределами синего круга представляет утверждение, а не A и т. Д.

Мы можем построить область, соответствующую утверждению not (A или (B and not C)), пошагово, как мы вычисляли таблицу истинности:

Заштрихованные области представляют не C, B и не C, A или (B, а не C), не (A или (B, а не C)).

Аналогичным образом мы можем графически продублировать вычисление таблицы истинности не A и (не B или C):

Заштрихованные области представляют не B, не B или C, не A, не A и (не B или C).

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

Диаграммы Венна для более чем трех операторов

На диаграмме Венна с тремя утверждениями три круга и область за их пределами делят «вселенную» на восемь областей. Каждую область можно охарактеризовать тем, находятся ли ее точки внутри или снаружи A, B или C: каждая область соответствует уникальной тройной области и, идя от не A и не B, и не C (снаружи) к A, B и C ( самое сокровенное).Обычное название этих выражений — союзов или, по аналогии с умножением, одночленов . Более того, в диаграмме Венна с тремя утверждениями относительная топология этих областей отражает относительную близость соответствующих одночленов в следующем точном смысле: если два одночлена отличаются переключением одного утверждения на его отрицание, две соответствующие области имеют общую край. Мы будем называть такую диаграмму Венна топологически точной. Топологически точные диаграммы существуют для одного, двух или трех утверждений, но не, если число утверждений равно четырем или более; несуществование доказано в Приложении.

На этом рисунке показан один из стандартных способов построения диаграммы Венна для четырех операторов A, B, C, D; области, соответствующие A и B, а не C и не D, и A, B и C, но не D, не являются смежными, даже если соответствующие одночлены различаются только в одном месте. Независимо от того, как нарисованы кривые, это явление будет происходить.

Топологически точные диаграммы Венна в более высоких измерениях

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

Топологически точная «диаграмма Венна» для четырех утверждений A, B, C, D: окружности плоской диаграммы Венна с тремя утверждениями лежат в плоскости (x, y) и утолщаются в цилиндры вверх и вниз вдоль ось z.Это не меняет их относительную топологию. Четвертый цилиндр размещен нижней стороной в плоскости (x, y) так, чтобы охватить верхнюю часть цилиндров. Это разбивает каждую из исходных областей на две половины: D, а не D, которые имеют общую грань в плоскости.

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

Приложение

На плоской диаграмме Венна с тремя операторами обозначим точку в каждой из восьми областей соответствующим мономом и проведем отрезок прямой между двумя из этих точек, если области имеют общую сторону.Полученный таким образом граф является двойным графом разбиения на области; по построению никакие два ребра не пересекаются. Сам граф можно перерисовать как вершины и ребра куба, со смещением по оси x, соответствующим A <-->, а не с примыканием соответствующих областей, смещение по оси y, соответствующим B <--> не B-смежность, а смещение в z-направлении, соответствующее C <--> не C-смежности.

Точка в каждом регионе помечена соответствующим одночленом, аббревиатурой и знаком &, а не знаком ~.Двойственный граф с этими точками как вершинами и ребрами, соответствующими смежным областям, может быть перерисован как вершины и ребра 3-мерного куба.

В топологически точной диаграмме Венна для 4 операторов A, B, C, D двойственный граф будет иметь 16 вершин, помеченных не A, не B, не C и не D до A, B, C и D. Каждый регион должен иметь общий край ровно с четырьмя другими регионами, так как есть 4 места, где «не» можно вставить или удалить.Соответственно, дуальный граф должен показывать 4 возможных направления в каждой вершине; это дает график ребер 4-мерного куба.

Двойственный граф топологически точной 4-утвержденной диаграммы Венна — это граф ребер 4-мерного куба. Здесь для сжатия обозначений вершина помечается ее координатами (0 или 1) в направлениях A, B, C и D. Четвертый куб рисуется как спроецированный в трехмерное пространство; края, уходящие в 4-е измерение, показаны зеленым.

Если бы на плоскости можно было нарисовать совершенную диаграмму Венна для 4 логических переменных, то на плоскости можно было бы нарисовать дуальный граф, граф ребер 4-куба, без пересечений ребер; так же, как это произошло с диаграммой Венна с 3 переменными и графом ребер 3-куба.

Это невозможно, потому что граф ребер 4-куба содержит K ₅, полный граф с 5 вершинами. («Полный» означает, что у каждого есть ребро, соединяющее его с четырьмя другими).Следующие два изображения показывают K ₅ и его вложение как подграф графа ребер 4-куба.

Поскольку граф K ₅ может быть вложен в граф ребер 4-куба, топологически точная диаграмма Венна с 4 переменными вложит K ₅ в плоскость; это, как известно, невозможно.

Вот где можно обнаружить противоречие: граф K ₅ не может быть нарисован на плоскости без пересечения двух его ребер.Обычное доказательство этого факта использует теорему Жордана о кривой (каждая простая замкнутая кривая делит плоскость на две области: одну «внутри» кривой и одну «снаружи») и теорему Эйлера (если V, E и F — числа вершины, ребра и грани плоского графа, то V — E + F = 2). Вот более элементарный аргумент.

Первые три вершины K ₅ имеют три ребра, образующих треугольник. По теореме Жордана о кривой (она нам нужна только для криволинейных многоугольников; гораздо проще доказать, чем общее утверждение), треугольник делит плоскость на внутреннюю и внешнюю.Предположим, что четвертая вершина уходит внутрь. Затем его ребра к первым трем вершинам делят этот треугольник на три области. Теперь пятую вершину поставить некуда. Если он снаружи, его нельзя соединить с четвертым, но если он внутри, он должен лежать в одном из трех треугольников. Этот треугольник будет использовать четвертую и две вершины исходных вершин, но тогда пятая вершина не будет соединяться с оставшейся исходной вершиной.

Пятую вершину поставить некуда: Граф K ₅ не может быть вложен в плоскость.

Тони Филлипс
Университет Стоуни-Брук,
, тони, math.sunysb.edu,

ПРИМЕЧАНИЕ: Те, кто имеет доступ к JSTOR, могут найти там некоторые из упомянутых выше документов. Для тех, у кого есть доступ, MathSciNet Американского математического общества может быть использован для получения дополнительной библиографической информации и обзоров некоторых этих материалов. К некоторым из вышеперечисленных элементов можно получить доступ через портал ACM, который также предоставляет библиографические услуги.

Введение в цифровую логику — Глава книги

Аналоговый сигнал является непрерывным, а цифровой — дискретным.В частности, аналоговый сигнал представляет собой бесконечный континуум уровней, а цифровой — конечные дискретные уровни.

Наш мир по своей сути аналоговый. Мы воспринимаем непрерывные уровни сигнала, такие как интенсивность света или звука. Напротив, если бы люди родились с цифровыми органами чувств, мы бы ощущали только двоичные состояния, например яркость или темноту, тишину или шум. Неудивительно, что большинство из нас, кому посчастливилось пользоваться функционирующими аналоговыми органами чувств, никогда не захотят променять их на цифровые.Основываясь на этом наблюдении, можно сделать вывод, что по сравнению с аналоговыми технологиями цифровая технология по своей природе ограничена и сыровата. Тем не менее, преобладающая тенденция в технологии явно отдает предпочтение цифровому подходу по сравнению со «старым» аналоговым, что указывает на значительные преимущества этой «новой» технологии. Давайте рассмотрим основные преимущества с помощью следующей аналогии.

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

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

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

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

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

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

Он также подчеркивает другой аспект цифровой технологии, а именно: чем больше сигналов или битов мы соглашаемся использовать в нашей последовательности, тем точнее мы можем выразить эти уровни. Однако до тех пор, пока мы вынуждены использовать конечную последовательность битов, количество уровней, которые мы можем выразить, также будет конечным. Возвращаясь к нашей аналогии с трафиком, в то время как с помощью одного бита мы можем выразить только два уровня, «хорошо» или «сердитый», с помощью всего двух битов мы можем сигнализировать о четырех уровнях: «хорошо», «слегка раздражен», «несколько раздражен» и ‘сердитый’.

Еще одно преимущество цифровых технологий перед аналоговыми — это легкость, с которой данными можно манипулировать с помощью очень простых «операторов», называемых вентилями , имитирующими математические операции.

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

Когда мы говорим о двоичном состоянии бита, мы будем использовать обычные метки «включено» или «выключено», «1» или «0», или «высокий» или «низкий» (которые иногда также записываются как « HI ‘или’ LO ‘).Мы будем использовать эти метки взаимозаменяемо и согласимся с тем, что «on», «1» и «high» считаются эквивалентными, а также «off», «0» и «low».

В физической среде, такой как электронная схема, существуют явные стандарты уровня напряжения или тока для определенного цифрового логического состояния. Существует множество соглашений, наиболее распространенные из которых перечислены в таблице 1.1. Для экономии энергии и увеличения скорости переключения стандарт низковольтной транзисторно-транзисторной логики (TTL) 3,3 В все чаще заменяет старый, установленный уровень TTL 5 В.

Таблица 1.1. Чаще всего используются цифровые стандарты напряжения.

Логический уровень	3,3 В CMOS ИЛИ TTL	5 В TTL
1, на, высокий	3,3 В	5 В
0, выкл., Низкий	0 В	0 В

Таблица 1.1 намеренно сделана простой, и в ней не перечислены допустимые пороговые уровни для высоких и низких входных и выходных сигналов.Обычно они находятся в пределах одного вольта от «идеальных» уровней, перечисленных выше. Например, для систем CMOS 3,3 В входное напряжение от 0 до 0,8 В приемлемо в качестве входа низкого уровня, сигналы между 2,0 и 3,3 В считаются входом высокого уровня; вы хотите избежать уровней входного сигнала между 0,8 В и 2,0 В, потому что они неоднозначны.

Дискретным компонентам требуется внешнее питание, и указанные выше уровни указывают их напряжения питания.

Наконец, избегайте подачи входных сигналов, превышающих высокий или низкий уровни, указанные выше.Это может привести к повреждению компонентов!

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

Платформа без меток и ферментов с видимым выходом для создания универсальных логических вентилей с использованием G-квадруплекса в клетке в качестве преобразователя сигналов.

Chem Sci. 14 января 2018 г .; 9 (2): 300–306.

, ^a, ^a и ^a

Цзюньхуа Чен

^a Ключевая лаборатория комплексного контроля и управления агроэкологическим загрязнением в Гуандуне, Гуандунский институт экологических наук и технологий, Гуанчжоу 510650, Китай .Электронная почта: moc.361@auhnujnehc222

Цзяфэн Пан

^a Гуандунская ключевая лаборатория комплексного контроля и управления агроэкологическим загрязнением, Гуандунский институт экологических наук и технологий, Гуанчжоу 510650, Китай. Электронная почта: moc.361@auhnujnehc222

Шу Чен

^a Гуандунская ключевая лаборатория комплексного контроля и управления агроэкологическим загрязнением, Гуандунский институт экологических наук и технологий, Гуанчжоу 510650, Китай.Электронная почта: moc.361@auhnujnehc222

Поступило 12.09.2017 г .; Принята в печать 18 октября 2017 г. Эта статья находится под лицензией Creative Commons Attribution 3.0 Непортированная лицензия (CC BY 3.0)

Эта статья цитируется в других статьях PMC.

Abstract

Полный набор двоичных базовых логических вентилей (OR, AND, NOR, NAND, INHIBT, IMPLICATION, XOR и XNOR) реализован на платформе считывания без меток и ферментов с использованием клеточного G-квадруплекса в качестве сигнала. преобразователь. При наличии соответствующего входа временно заблокированная G-богатая последовательность в шпильке ДНК высвобождается посредством расщепления синергетически-стабилизированным Mg ²⁺-зависимым ДНКзимом, который можно заставить функционировать через кооператив , управляемый входом. соединение субъединиц ДНКзима.В присутствии гемина неблокированный G-квадруплексный ДНКзим катализирует окисление 3,3 ‘, 5,5’-тетраметилбензидина (TMB) H ₂ O ₂ с образованием цветного сигнала считывания, который можно легко различить невооруженным глазом. Эта стратегия довольно универсальна и проста для логических операций. Два комбинаторных логических элемента (XOR + AND и XOR + NOR) также успешно изготовлены для демонстрации модульности и масштабируемости вычислительных элементов. Отличительным преимуществом этой логической системы является то, что молекулярные события в водном растворе можно преобразовать в изменение цвета, которое можно наблюдать невооруженным глазом, не прибегая к аналитическим приборам.Более того, эта работа раскрывает новый путь проектирования молекулярных логических вентилей, которые могут быть выполнены без какой-либо процедуры маркировки и иммобилизации или этапа разделения и промывки, что имеет большие перспективы для интеллектуальной диагностики в местах оказания медицинской помощи и приложений в полевых условиях.

Введение

Молекулярные логические вентили, которые способны выполнять вычислительные операции, могут быть использованы в химическом / биологическом зондировании, диагностике заболеваний и интеллектуальной визуализации и, таким образом, привлекли значительный исследовательский интерес.1–7 К настоящему времени успешно реализованы различные базовые логические вентили, усовершенствованные схемы и даже нейронные сети, что доказывает потенциал молекулярных логических вентилей в науке о биокомпьютинге. 8–14 Однако потребность в сложных процедурах маркировки или модификации, 15 , 16 скоропортящихся белковых ферментов17,18 и считывание показаний, зависящих от приборов19,20, препятствуют развитию молекулярных вычислений и их приложений для обнаружения и мониторинга на месте. Таким образом, создание сенсорной платформы без меток и ферментов для создания универсальных логических вентилей без использования каких-либо аналитических инструментов является привлекательным и остро необходимым.

Имитирующий пероксидазу G-квадруплекс ДНКзим является идеальным преобразователем сигнала для создания логических ворот ДНК и функциональных устройств ДНК. 21-25 После инкубации с гемином образованный гибрид G-квадруплекс / гемин способен катализировать окисление 3 , 3 ‘, 5,5’-тетраметилбензидин (TMB) с помощью H ₂ O ₂ и вызвать изменение цвета с бесцветного на синий26,27 По сравнению с зависящими от прибора флуоресцентными и электрохимическими сигналами для непрямых выходов, 28,29 G-quadruplex обеспечивает прямое и видимое считывание, которое легко распознается невооруженным глазом.30,31 Каталитическая структура G-квадруплекса происходит из неблокированной G-богатой одноцепочечной ДНК, образование которой можно контролировать с помощью реакций гибридизации и замещения клеточных G-богатых последовательностей.32,33 В последние годы появились некоторые изящные сенсорные платформы. были успешно разработаны с использованием G-квадруплекса в качестве репортера сигналов.34–38 Однако не существует испытаний для изготовления полного набора логических вентилей, особенно для интегральных схем, использующих G-квадруплекс в клетке в качестве преобразователя сигнала для выдачи видимых сигналов. Результаты.В этом исследовании мы построили серию логических вентилей на сенсорной платформе без меток и ферментов, используя G-квадруплекс в клетке в качестве преобразователя сигнала. Логические события в системе можно легко преобразовать в изменения цвета, которые можно отслеживать невооруженным глазом. Предлагаемая здесь логическая стратегия проста в эксплуатации без какой-либо процедуры маркировки и иммобилизации или этапа разделения и промывки, требуя только смешивания нескольких растворов при комнатной температуре для получения интуитивно понятных и видимых результатов, и поэтому она имеет большие перспективы для обнаружения POC и на месте мониторинг.

Результаты и обсуждение

Mg ²⁺-зависимые субъединицы ДНКзима 39–41 (домены I и II) используются в качестве вычислительных элементов для создания универсального набора логических вентилей. Отделенная субъединица не может собираться с образованием активного ДНКзима. В присутствии соответствующей входной ДНК субъединицы могут собираться в активные структуры ДНКзима посредством процессов кооперативной гибридизации , управляемых входом. Полученный ДНКзим расщепляет ДНК-субстрат, содержащий рибонуклеооснование (rA), в присутствии Mg ²⁺ для генерации выходных сигналов.изображает конструкцию логического элемента XOR. Система состоит из субъединиц ДНКзима ДНК1 / ДНК2 и ДНК3 / ДНК4, субстрата ДНК5 и исходной ДНК. В отсутствие ввода (0, 0) субъединицы не могут спонтанно образовывать какую-либо активную структуру ДНКзима. В присутствии input1 (1, 0) или input2 (0, 1) образуются два разных ДНКзима, что приводит к расщеплению шпилечного ДНК-субстрата на участке рибонуклеооснования. Затем высвобождается и активируется заключенная в клетку последовательность ДНКзима, имитирующая пероксидазу хрена G-квадруплекс (синий сегмент в ДНК5) в стволовой структуре шпильки.После инкубации с гемином G-квадруплексный ДНКзим катализирует окисление TMB H ₂ O ₂ с образованием цветного считывающего сигнала, который можно легко различить невооруженным глазом. При наличии обоих входов (1, 1) дуплекс между inptut1 и input2 будет сформирован, поскольку они дополняют друг друга. В этом случае образование каталитически активного ДНКзима запрещено. показаны типичные фотографии ворот XOR. изображает спектры поглощения от 500 до 800 нм.показывает соответствующую интенсивность поглощения при λ = 650 нм. Интенсивность поглощения 0,1 определяется как пороговое значение для всех логических вентилей для определения положительных и отрицательных выходных сигналов. Когда значение поглощения при λ = 650 нм ниже порогового значения 0,1, выходной сигнал вычислительной системы считается равным «0» (ложный выходной сигнал). Если интенсивность поглощения выше 0,1, на выходе отображается «1» (истинный выходной сигнал).

Схематическое изображение логического элемента XOR, который состоит из субъединиц ДНКзима (ДНК1 – ДНК4), субстрата (шпилька ДНК5, клеточная последовательность G-квадруплекса в стволовой структуре шпильки показана синим цветом) и входной ДНК .На протяжении всей статьи домены X и X ‘в цепях ДНК представляют собой области комплементарных пар оснований. Домены I и II являются каталитическими коровыми компонентами Mg ²⁺ -зависимых субъединиц ДНКзима.

(A) Фотографии логического элемента XOR с различными комбинациями входов. (B) Спектры поглощения этого логического элемента. (C) Столбчатая диаграмма соответствующих интенсивностей поглощения при λ = 650 нм. Черная пунктирная линия показывает пороговое значение 0,1.(D) Таблица истинности ворот XOR. (E) Электронная эквивалентная схема.

Решение системы стало синим (output = 1) только после активации только input1 или input2, что характеризует вентиль XOR. Таблица истинности и схемы приведены соответственно.

Логический вентиль OR изготавливается с использованием четырех субъединиц ДНКзима (ДНК1 – ДНК4) и субстрата шпильки (ДНК5) в качестве вычислительных элементов. Как показано на фиг.1, input1 комплементарен плечам распознавания субъединиц ДНКзима ДНК1 и ДНК2, а input2 комплементарен плечам распознавания субъединиц ДНКзима ДНК3 и ДНК4.Следовательно, добавление либо input1, либо input2, либо обоих входов вызывает образование одного или двух каталитических ДНКзимов, которые кооперативно стабилизируются компонентами вход / субстрат, что приводит к расщеплению шпильки ДНК5 и генерации колориметрических сигналов. показаны типичные фотографии ворот операционной. изображает спектры поглощения от 500 до 800 нм. показывает соответствующую интенсивность поглощения при λ = 650 нм. Логический вентиль ИЛИ представлен ситуацией, когда выход равен 1, если один или оба входа равны 1.Таблица истинности и схемы приведены соответственно.

Схематическое изображение логического элемента ИЛИ, который состоит из субъединиц ДНКзима (ДНК1 – ДНК4), субстрата (шпилька ДНК5, клеточная последовательность G-квадруплекса в стволовой структуре шпильки обозначена синим цветом) и входной ДНК .

(A) Фотографии логического элемента ИЛИ с различными комбинациями входов. (B) Спектры поглощения этого логического элемента. (C) Столбчатая диаграмма соответствующих интенсивностей поглощения при λ = 650 нм.Черная пунктирная линия показывает пороговое значение 0,1. (D) Таблица истинности ворот операционной. (E) Электронная эквивалентная схема.

показывает конструкцию логического элемента И. Эта система состоит из двух субъединиц ДНКзима (ДНК1 и ДНК2), субстрата ДНК3 и исходной ДНК. Вход1 и вход2 частично комплементарны двум субъединицам, поэтому, когда вход1 или вход2 добавляется к логическому элементу И по отдельности, эти входы сами по себе не могут собрать субъединицы в активный ДНКзим.Такая частичная гибридизация приводит к бесцветному раствору, и на выходе отображается 0. При наличии обоих входов (1, 1) перекрестная гибридизация между сегментами C и C ‘входов позволяет кооперативному связыванию двух субъединиц, что приводит к синергетически-стабилизированный активный ДНКзим. показаны типичные фотографии ворот AND. изображает спектры поглощения от 500 до 800 нм. показывает соответствующую интенсивность поглощения при λ = 650 нм. Логический вентиль И представлен ситуацией, когда выход равен 1, только если оба входа равны 1.Таблица истинности и схемы приведены соответственно. Чтобы исследовать влияние pH и ионной силы на отклик логической системы, состояние (1, 1) логического элемента AND было протестировано при различных значениях pH и ионной силе (рис. S1, ESI ^†). Взяв в качестве примера логический вентиль И, формирование структуры G-квадруплекса в логической системе было подтверждено спектроскопией кругового дихроизма (КД) (рис. S2, ESI ^†).

Схематическое изображение логического элемента И, который состоит из субъединиц ДНКзима (ДНК1 и ДНК2), субстрата (шпилька ДНК3, клеточная последовательность G-квадруплекса в стволовой структуре шпильки обозначена синим цветом) и входной ДНК .

(A) Фотографии логического элемента И с различными комбинациями входов. (B) Спектры поглощения этого логического элемента. (C) Столбчатая диаграмма соответствующих интенсивностей поглощения при λ = 650 нм. Черная пунктирная линия показывает пороговое значение 0,1. (D) Таблица истинности ворот AND. (E) Электронная эквивалентная схема.

Базовые логические элементы могут быть коррелированы для демонстрации функций более высокого порядка, таких как комбинаторные схемы (конструкция логических элементов XNOR, NAND, NOR, INHIBIT и IMPLICATION изображена на рис.S3 – S12 в ESI ^†). иллюстрирует работу комбинированного логического элемента XOR и AND, который обеспечивает общее логическое поведение OR. В присутствии input1 или input2 два активных ДНКзима образуются посредством управляемой вводом кооперативной гибридизации соответствующих субъединиц ДНКзима (ДНК1, NDA2, ДНК3 и ДНК4). Это приводит к расколу субстрата и дает истинный результат. При запуске системы с обоими входами четыре субъединицы ДНКзима (ДНК1 – ДНК4) не могут собираться в активную структуру ДНКзима из-за предпочтительной гибридизации между входами.Однако гибридизация между двумя входами может сблизить домены E и F и вызвать образование другого синергетически стабилизированного активного ДНКзима из субъединиц ДНК5 / ДНК6. Таким образом, интегральная схема, созданная из вентилей XOR и AND, может работать параллельно в одной пробирке с использованием одного и того же набора входов. показывает типичные фотографии логического элемента XOR + AND. изображает спектры поглощения от 500 до 800 нм. показывает соответствующую интенсивность поглощения при λ = 650 нм.Комбинаторная схема имеет выход 1, если один или оба входных сигнала равны 1, и поэтому при работе она ведет себя как логический элемент ИЛИ. Таблица истинности и схемы приведены соответственно.

Схематическое изображение логического элемента XOR + AND, который состоит из субъединиц ДНКзима (ДНК1 – ДНК6), субстрата (шпилька ДНК7, клеточная последовательность G-квадруплекса в стволовой структуре шпильки показана синим цветом) и ввод ДНК.

(A) Фотографии логического элемента XOR + AND с различными комбинациями входов.(B) Спектры поглощения этого логического элемента. (C) Столбчатая диаграмма соответствующих интенсивностей поглощения при λ = 650 нм. Черная пунктирная линия показывает пороговое значение 0,1. (D) Таблица истинности логического элемента XOR + AND. (E) Электронная эквивалентная схема.

Также разработана другая интегральная схема, состоящая из параллельных логических вентилей XOR и NOR для обеспечения общего логического поведения NAND. Принцип показан в. При отсутствии ввода матричная ДНК1 гибридизируется с субъединицами ДНКзима (ДНК6 и ДНК7) для создания активной структуры ДНКзима, которая расщепляет субстрат (ДНК8) и дает на выходе 1.В присутствии либо input1, либо input2, ввод может демонтировать сформированную активную структуру ДНКзима от матрицы ДНК1 посредством реакции смещения цепи, опосредованной пальцами ног, с использованием сегментов E и H в качестве связывающих доменов toehold. Однако субъединицы (ДНК2, ДНК3, ДНК4 и ДНК5) могут собираться в две другие активные структуры ДНКзима посредством процессов кооперативной гибридизации , управляемых вводом. Это приводит к расщеплению субстрата (ДНК8), а также дает истинный результат. В присутствии обоих входов шесть субъединиц ДНКзима (ДНК2 – ДНК7) не могут собираться в какую-либо активную структуру ДНКзима из-за предпочтительной гибридизации между входами и реакций замещения между матрицей и входами.Это приводит к выходу 0. Таким образом, параллельная активация комбинаторной схемы, установленной вентилями XOR и NOR, может быть реализована в одной системе с использованием того же набора входов. показывает типичные фотографии ворот XOR + NOR. изображает спектры поглощения от 500 до 800 нм. показывает соответствующую интенсивность поглощения при λ = 650 нм. Комбинаторная схема имеет выход 0 только в том случае, если оба входных сигнала равны 1, и поэтому она ведет себя как вентиль И-НЕ в работе. Таблица истинности и схемы приведены соответственно.

Схематическое изображение логического элемента XOR + NOR, который состоит из матрицы ДНК (ДНК1), субъединиц ДНКзима (ДНК2 – ДНК7), субстрата (шпилька ДНК8, клеточная последовательность G-квадруплекса в стволовой структуре шпильки обозначен синим цветом) и входной ДНК.

(A) Фотографии логического элемента XOR + NOR с различными комбинациями входов. (B) Спектры поглощения этого логического элемента. (C) Столбчатая диаграмма соответствующих интенсивностей поглощения при λ = 650 нм.Черная пунктирная линия показывает пороговое значение 0,1. (D) Таблица истинности ворот XOR + NOR. (E) Электронная эквивалентная схема.

Чтобы продемонстрировать возможность использования логической системы для практических приложений, логические вентили XOR, OR, AND и XOR + AND были проверены на образцах сыворотки человека. В качестве входных данных использовались Input1 и input2 в 10% сыворотке. Результаты показывают, что логическая система также может эффективно выполнять эти вычислительные функции в сыворотке крови человека (рис. S13 – S16, ESI ^†).Эти результаты показывают, что предложенная логическая система хорошо работает даже в относительно сложных матрицах образцов и на нее не влияет, когда входные данные находятся в образцах сыворотки человека.

Выводы

В заключение, универсальный набор элементарных логических вентилей с двумя входами (OR, AND, NOR, NAND, INHIBT, IMPLICATION, XOR и XNOR) был успешно построен на платформе биокомпьютера без меток и ферментов. . Используя G-квадруплекс в клетке в качестве преобразователя сигнала, результат вычисления может быть однозначно считан невооруженным глазом.Уникальность логической системы заключается в управляемой вводом сборке и разборке вычислительных схем, модульности конструкции затвора и видимом выходе, который можно получить, наблюдая за изменением цвета решения. Исследование продемонстрировало универсальность и масштабируемость вычислительных элементов путем построения двух комбинаторных вентилей. Мы соединяем вентили XOR и AND в многоуровневую схему (XOR + AND), которая обеспечивает общее поведение логического элемента OR. Также разработана другая интегральная схема, состоящая из параллельных логических вентилей XOR и NOR (XOR + NOR) для выполнения окончательного сетевого анализа NAND.Описанная здесь стратегия строительства проста по конструкции и экономична в эксплуатации без какой-либо процедуры маркировки и иммобилизации или этапа разделения и промывки, требуя только смешивания нескольких растворов при комнатной температуре для получения интуитивно понятных и видимых результатов, и поэтому она имеет большие перспективы для интеллектуальных Диагностика POC и мониторинг на месте.

Заявление о живом испытуемом

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

Конфликт интересов

Авторы заявляют об отсутствии конкурирующих финансовых интересов.

Дополнительные материалы

Дополнительные сведения

Благодарности

Финансовая поддержка была предоставлена NSFC (21407029), Фондами естественных наук провинции Гуандун для выдающихся молодых ученых (2016A030306012), Специальной программой поддержки молодых талантливых ученых провинции Гуандун (2015TQ01Z092), специальный проект GDAS по развитию науки и технологий (2017GDASCX-0405), Программа науки и технологий Гуанчжоу (201508020010), Программа науки и технологий провинции Гуандун (2016B070701015) и программа SPICC (2016GDASPT-0105).

Ссылки

ДельРоссо Н. В., Хьюс С., Спектор Л., Дерр Н. Д. Энджью. Chem., Int. Эд. 2017; 56: 4443–4446. [PubMed] [Google Scholar]
Герасимова Ю.В., Колпащиков Д.М. Ангью. Chem., Int. Эд. 2016; 55: 10244–10247. [PubMed] [Google Scholar]
Хемфилл Дж., Дейтерс А. Дж. Ам. Chem. Soc. 2013; 135: 10512–10518. [PubMed] [Google Scholar]
Фэн Л., Лю З., Оффенхауссер А., Майер Д. Энгью. Chem., Int. Эд. 2015; 54: 7693–7697. [PubMed] [Google Scholar]
Pu F., Ren J., Qu X. Adv. Матер. 2014; 26: 5742–5757. [PubMed] [Google Scholar]
Lilienthal S., Klein M., Orbach R., Willner I., Remacle F., Levine R.D. Chem. Sci. 2017; 8: 2161–2168. [Бесплатная статья PMC] [PubMed] [Google Scholar]
Wang F., Lu C., Willner I. Chem. Ред. 2014; 114: 2881–2941. [PubMed] [Google Scholar]
Цянь Л., Винфри Э. Наука. 2011; 332: 1196–1201. [PubMed] [Google Scholar]
Цянь Л., Винфри Э., Брук Дж. Природа. 2011; 475: 368–372. [PubMed] [Google Scholar]
Би С., Чен М., Цзя X., Дун Й., Ван З. Ангью. Chem., Int. Эд. 2015; 54: 8144–8148. [PubMed] [Google Scholar]
Wang W., Huang S., Li J., Rui K., Bi S., Zhang J., Zhu J. Chem. Sci. 2017; 8: 174–180. [Бесплатная статья PMC] [PubMed] [Google Scholar]
Zhang C., Yang J., Jiang S., Liu Y., Yan H. Nano Lett. 2016; 16: 736–741. [PubMed] [Google Scholar]
Ю М., Чжу Г., Чен Т., Донован М. Дж., Тан В. Дж. Ам. Chem. Soc. 2015; 137: 667–674. [Бесплатная статья PMC] [PubMed] [Google Scholar]
Mailloux S., Герасимова Ю.В., Гуз Н., Колпащиков Д.М., Кац Э. Ангью. Chem., Int. Эд. 2015; 54: 6562–6566. [Бесплатная статья PMC] [PubMed] [Google Scholar]
Guo Y., Wu J., Ju H. Chem. Sci. 2015; 6: 4318–4323. [Бесплатная статья PMC] [PubMed] [Google Scholar]
Chen J., Fang Z., Lie P., Zeng L. Anal. Chem. 2012; 84: 6321–6325. [PubMed] [Google Scholar]
Zhu J., Wang L., Xu X., Wei H., Jiang W. Anal. Chem. 2016; 88: 3817–3825. [PubMed] [Google Scholar]
Ge L., Wang W., Sun X., Хоу Т., Ли Ф. Анал. Chem. 2016; 88: 9691–9698. [PubMed] [Google Scholar]
Чжан П., Хэ З., Ван К., Чен Дж., Чжао Дж., Чжу Х., Ли К., Мин К., Чжу Дж. ACS Nano. 2015; 9: 789–798. [PubMed] [Google Scholar]
Чен Дж., Цзэн Л. Биосенс. Биоэлектрон. 2013; 42: 93–99. [PubMed] [Google Scholar]
Чен Дж., Чжоу С., Вен Дж. Ангью. Chem., Int. Эд. 2015; 54: 446–450. [PubMed] [Google Scholar]
Zhu J., Zhang L., Li T., Dong S., Wang E. Adv. Матер. 2013; 25: 2440–2444. [PubMed] [Google Scholar]
Zhu J., Чжан Л., Донг С., Ван Э. ACS Nano. 2013; 7: 10211–10217. [PubMed] [Google Scholar]
Zhu J., Zhang L., Zhou Z., Dong S., Wang E. Anal. Chem. 2014; 86: 312–316. [PubMed] [Google Scholar]
Nie J., Zhao M., Xie W. J., Cai L., Zhou Y., Zhang X. Chem. Sci. 2015; 6: 1225–1229. [Бесплатная статья PMC] [PubMed] [Google Scholar]
Fan D., Wang E., Dong S. Chem. Sci. 2017; 8: 1888–1895. [Бесплатная статья PMC] [PubMed] [Google Scholar]
Chen J., Wen J., Yang G., Zhou S. Chem.Commun. 2015; 51: 12373–12376. [PubMed] [Google Scholar]
Вен В., Ян X., Чжу К., Ду Д., Лин Ю. Анал. Chem. 2017; 89: 138–156. [PubMed] [Google Scholar]
Zhang H., Zhang H., Aldalbahi A., Zuo X., Fan C., Mi X. Biosens. Биоэлектрон. 2017; 89: 96–106. [PubMed] [Google Scholar]
Fan D., Wang K., Zhu J., Xia Y., Han Y., Liu Y., Wang E. Chem. Sci. 2015; 6: 1973–1978. [Бесплатная статья PMC] [PubMed] [Google Scholar]
Du Y., Jiang H., Huo Y., Han G., Kong D. Biosens.Биоэлектрон. 2016; 77: 971–977. [PubMed] [Google Scholar]
Li D., Cheng W., Li Y., Xu Y., Li X., Yin Y., Ju H., Ding S. Anal. Chem. 2016; 88: 7500–7506. [PubMed] [Google Scholar]
Zhuang J., Lai W., Chen G., Tang D. Chem. Commun. 2014; 50: 2935–2938. [PubMed] [Google Scholar]
Ма Д., Кван М. Х., Чан Д. С., Ли П., Ян Х., Ма В. П., Бай Л., Цзян З., Леунг К. Аналитик. 2011; 136: 2692–2696. [PubMed] [Google Scholar]
Ли Т., Донг С., Ван Э. Анал. Chem. 2009. 81: 2144–2149.[PubMed] [Google Scholar]
Ван М., Мао З., Кан Т., Вонг К., Мергни Дж., Люн К., Ма Д. Chem. Sci. 2016; 7: 2516–2523. [Бесплатная статья PMC] [PubMed] [Google Scholar]
Zhao C., Wu L., Ren J., Qu X. Chem. Commun. 2011; 47: 5461–5463. [PubMed] [Google Scholar]
Леунг К., Хе Х., Ван В., Чжун Х., Чан Д. С., Люн К., Ма Д. ACS Appl. Матер. Интерфейсы. 2013; 5: 12249–12253. [PubMed] [Google Scholar]
Эльбаз Дж., Любашевски О., Ван Ф., Ремакл Ф., Левин Р.D., Willner I. Nat. Nanotechnol. 2010; 5: 417–422. [PubMed] [Google Scholar]
Орбах Р., Виллнер Б., Виллнер И. Chem. Commun. 2015; 51: 4144–4160. [PubMed] [Google Scholar]
Орбах Р., Лилиенталь С., Кляйн М., Левин Р. Д., Ремакл Ф., Виллнер И. Хим. Sci. 2015; 6: 1288–1292. [Бесплатная статья PMC] [PubMed] [Google Scholar]

Логические ворота NAND, NOR и XOR — видео и стенограмма урока

Логические вентили И-НЕ, ИЛИ-ИЛИ и ИСКЛЮЧАЮЩЕЕ ИЛИ

Отрицательная операция И или вентиль И-НЕ является двоичным дополнением операции И:

И-НЕ (X, Y) = НЕ (И (X, Y))

Поскольку операция НЕ является обратимой, это соотношение также можно записать как:

И (X, Y) = НЕ (И-НЕ (X, Y))

Точно так же вентиль ИЛИ-ИЛИ определяется как операция ИЛИ с отрицанием:

ИЛИ (X, Y) = NOT (OR (X, Y))

OR также может быть выражено в терминах NOR:

OR (X, Y) = NOT (NOR (X, Y))

Определение операция ИЛИ состоит в том, что он ИСТИНА, если какой-либо вход ИСТИНА.Это включает возможность того, что оба входа ИСТИННЫ. Напротив, операция исключающее ИЛИ или вентиль XOR (иногда называемый EOR) имеет значение ИСТИНА тогда и только тогда, когда один вход является истиной.

Это отношение имеет два одинаково правильных выражения с точки зрения основных логических вентилей:

XOR (X, Y) = OR (AND (X, NOT (Y)), AND (NOT (X), Y)) = И (ИЛИ (X, Y), ИЛИ (НЕ (X), НЕ (Y)))

Таблицы истинности и характерные символы набора форм даны для И-НЕ, ИЛИ-ИЛИ и ИСКЛЮЧАЮЩЕГО ИЛИ на рисунке 2.Совершенно очевидно, что выходы И-НЕ и ИЛИ-ИЛИ являются точным дополнением И и ИЛИ, соответственно.

Рисунок 2: Таблицы истинности логических ворот и символы

Функциональная полнота

Если два входа логического элемента И-НЕ закорочены вместе, как показано на рисунке 3, единственными релевантными частями таблицы истинности будут те, для которых два входа равны.

Рисунок 3: Шлюз NAND, настроенный как шлюз НЕ

Это поведение в точности эквивалентно операции отрицания.Таким образом, вентиль НЕ может быть определен только в терминах логического элемента И-НЕ.

НЕ (X) = И-НЕ (X, X)

Это позволяет переформулировать логический элемент И в терминах только логических элементов И-НЕ.

AND (X, Y) = NAND (NAND (X, Y), NAND (X, Y))

Эквивалент логического элемента OR также может быть создан с использованием только логических элементов NAND, поместив две закороченных (эквивалентных NOT) NAND каждый вентиль на входе третьего логического элемента И-НЕ, как показано на рисунке 4.

Рисунок 4: Эквивалентная схема логического элемента ИЛИ только ИЛИ

Эта схема соответствует следующему уравнению только для NAND:

OR (X, Y) = NAND (NAND (X, X), NAND (Y, Y))

Аналогичный процесс можно повторить, используя только ИЛИ ворота.Оказывается, любой логический вентиль можно эмулировать, используя только вентили И-НЕ или только вентили ИЛИ-НЕ. Это свойство известно как функциональной полноты . Это означает, что вся логическая схема может быть построена с использованием только одного типа вентилей во всей конструкции. Вентили NAND и NOR также требуют наименьшего количества транзисторов в своей конструкции, что делает их эффективным выбором для больших микропроцессоров.

Итоги урока

Давайте сделаем несколько минут, чтобы повторить! Элементы

И , ИЛИ и НЕ вентили являются наиболее фундаментальными логическими вентилями, поскольку они относятся к трем базовым операциям логической логики.Однако дополнительные вентили, такие как NAND , NOR и XOR , предоставляют больше вариантов дизайна для логических схем с их уникальными таблицами истинности. Вентили И-НЕ и ИЛИ-ИЛИ представляют особый интерес, поскольку каждый из них может использоваться исключительно в схеме для имитации поведения любой другой логической операции. Это называется функциональной полнотой .

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

Аппаратное обеспечение компьютеров состоит из параллельных и последовательных операций логических вентилей, которые запускаются электронными входами.Эти функции могут дублироваться надлежащим образом спроектированными химическими или биологическими системами. Обсуждались различные молекулярные и супрамолекулярные сборки, которые работают как логические вентили и выполняют арифметические операции на молекулярном уровне (1–9). Точно так же биомолекулы, такие как нуклеиновые кислоты или белки, использовались в качестве активных компонентов, которые выполняют операции с логическим вентилем (10-15). Были разработаны искусственные схемы на основе генов, действующие как бистабильные тумблеры (16) или осцилляторы (17), и сообщалось о связанных системах фермент / ДНК, которые выполняют программируемые биохимические преобразования, имитирующие базовые вычисления конечного автомата (17).Использование ферментов в качестве активных компонентов для функций логических вентилей особенно интересно, потому что многочисленные биокаталитические циклы в природе полагаются на обработку информации, обнаруживая сходство с компьютерными устройствами. Хотя функция ферментных сетей как имитаторов логических вентилей обсуждалась (18) и рассматривалась возможность использования ферментов в качестве строительных единиц вычислительных архитектур высокой плотности (19), экспериментальная работа по проверке операций логических вентилей, стимулированных биокатализаторами, довольно редка и не имеет желаемой сложности, напоминающей компьютеры.Сообщалось об операциях с логическим вентилем на основе одного фермента. Например, динамические конформационные изменения малатдегидрогеназы в ответ на ионы Mg ⁺ и Ca ²⁺, действующие в качестве входных данных, были использованы для разработки логического элемента XOR (20). Кроме того, модифицированный фермент и его ингибитор были использованы в качестве входов, которые активируют логический элемент И (21). Недавно мы сообщали о сборке связанных биокаталитических систем, которые имитируют логические функции OR, XOR, AND или InhibAND (22), и использование этих систем для элементарных арифметических операций (полусумматор и полувычитатель) было продемонстрировано (23).Ни в одной из этих систем не было продемонстрировано последовательное функционирование нескольких вентилей, которые работают последовательно. Однако эта функция необходима для разработки любой будущей «компьютерной» функции повышенной сложности. Здесь мы сообщаем о сборке системы, связанной с четырьмя ферментами, которая включает в себя четыре входа и последовательно выполняет три операции логического элемента OR, AND и XOR.

Результаты и обсуждения

Система и ее работа изображены на рис. 1. A и состоит из четырех биокатализаторов, ацетилхолинэстеразы (AChE), холиноксидазы, микропероксидазы-11 (MP-11) и глюкозодегидрогеназы (GDH), связанных с ее парой кофакторов NAD ⁺ / NADH.Ацетилхолин (вход A) или бутирилхолин (вход B) гидролизуются AChE с образованием холина, который действует как выход первого логического элемента OR, рис. В . Холин, генерируемый вентилем ИЛИ и O ₂ (вход C), активирует вентиль И, который дает бетаиновый альдегид и H ₂ O ₂ в качестве продуктов. Отметим, что H ₂ O ₂ образуется только в присутствии O ₂ (рис. В ). Два биокатализатора MP-11 и GDH выполняют наиболее сложный логический элемент XOR, где два входа «1» дают выход «0».Входами для логического элемента XOR являются H ₂ O ₂, произведение логического элемента AND и глюкозы (вход D). Работа последовательности ворот считывается, следуя соотношению концентраций кофакторов NAD ⁺ / NADH, отслеживая оптическую плотность при λ = 340 нм. То есть, если только H ₂ O ₂ активирует систему, и глюкоза не добавляется, MP-11 катализирует окисление NADH до NAD ⁺, и NADH истощается. Точно так же, когда добавляется только глюкоза и вентиль AND не генерирует H ₂ O ₂, биокатализируемое GDH окисление глюкозы снижает NAD ⁺ до NADH, и поглощение NADH увеличивается.Когда H ₂ O ₂ и глюкоза (вход D) активируют пару MP-11 / GDH, катализируемое MP-11 окисление NADH до NAD ⁺ компенсируется опосредованным GDH / глюкозой восстановлением NAD ⁺ в NADH. Таким образом, чистое изменение концентрации НАДН не будет обнаружено (как требуется от логического элемента XOR). Модуль абсорбции A‖ NADH действует как сигнал считывания для операции логического элемента XOR.

Инжир.1.

Схема, описывающая работу конкатенированных логических вентилей на основе четырех связанных биокатализаторов ( A, ) и схемы для конкатенированной четырехферментной системы ( B ).

На рис. 2 показаны изменения оптической плотности НАДН в результате работы ряда вентилей при наличии четырех входов. Обратите внимание, что эти результаты представляют свойства оптимизированного состава концентраций различных биокатализаторов и соответствующих входных данных, которые учитывают специфические активности различных биокатализаторов.Рис. 2 A , кривая а, показывает характеристики поглощения НАДН в системе до активации различных биокатализаторов любым из входов. Это поглощение можно рассматривать как эталон для работы различных ворот. Рис. 2 A , кривая b, показывает характеристики поглощения при активации ворот OR ацетилхолином и, таким образом, активации ворот AND холином и O ₂ с получением H ₂ O ₂.Два биокатализатора MP-11 и GDH активируются H ₂ O ₂ и глюкозой в качестве входных данных. Поскольку окисление НАДН, катализируемое МР-11, компенсируется окислением глюкозы, катализируемым ГДГ, с сопутствующим образованием НАДН, значительного изменения поглощения НАДН не обнаруживается. Таким образом, системные входы (1, 0, 1, 1) приводят к выходу «0» в логическом элементе XOR. Рис. 2 B представляет выходные данные объединенных ворот в виде столбца абсорбции.Таким образом, выход для состояния (1, 0, 1, 1) представлен полосой b. Точно так же обмен ацетилхолина на бутирилхолин в качестве входа в вентиль OR дает холиновый продукт, который вместе с O ₂ активирует вентиль AND, что приводит к продукту H ₂ O ₂. Как и раньше, катализируемое МР-11 окисление НАДН с помощью Н ₂ О ₂ компенсируется GDH-опосредованным окислением НАД ⁺, и, таким образом, не обнаруживается никакого значительного чистого изменения абсорбции НАДН.Соответственно, состояние системы (0, 1, 1, 1) дает на выходе «0» (Рис. 2 B , столбец c). Когда вводятся оба входа логического элемента ИЛИ, а все другие входы активируют соответствующие ворота, состояние (1, 1, 1, 1), не наблюдается значительного изменения абсорбции НАДН, как и ожидалось (рис. 2). A , кривая d и 2 B , полоса d). Естественно, когда только O ₂ действует как ввод и никакой другой ввод не запускает какие-либо ворота, состояние (0, 0 1, 0), ни одна из биокатализируемых реакций не происходит, не наблюдается изменения в абсорбции НАДН и, таким образом, на выходе системы будет «0» (рис.2 A , кривая e и 2 B , бар e). Когда никакие входы не запускают логический элемент «ИЛИ», и только O ₂ и глюкоза действуют как входы, состояние системы (0, 0, 1, 1), холин не образуется и, таким образом, нет H ₂ O ₂. В результате происходит только катализируемое GDH окисление глюкозы с сопутствующим образованием NADH, о чем свидетельствует увеличение абсорбции системы (рис. A , кривая f и 2 B , бар f).Таким образом, выход логического элемента XOR равен «1». Активация системы ацетилхолином или бутирилхолоином в присутствии O ₂, но в отсутствие глюкозы состояния (1, 0, 1, 0) или (0, 1, 1, 0) приводят к образованию холина (в воротах ИЛИ) и последующее поколение H ₂ O ₂ (в воротах И). Образующийся H ₂ O ₂ активирует катализируемое MP-11 окисление НАДН. В отсутствие глюкозы на входе это состояние приводит к истощению абсорбции НАДН (рис.2 A , кривые g и h соответственно), что дает изменение значений модулей поглощения, как показано на рис. B , столбцы g и h соответственно. Таким образом, эти состояния приводят к выходу «1» логического элемента XOR. Естественно, когда два входа, ацетилхолин и бутирилхолин, активируют вентиль ИЛИ, а вентиль И активируется посредством O ₂, происходит образование H ₂ O ₂. Однако в отсутствие глюкозы образующийся H ₂ O ₂ истощает абсорбцию НАДН, что приводит к выходу «1» (рис.2 A , кривая i и 2 B , бар i). Отметим, что на рис. A , кривые a, f и e, помимо полосы поглощения НАДН при λ = 340 нм наблюдается дополнительная полоса при 410 нм. Эта полоса объясняется поглощением гемового центра, присутствующего в MP-11. Рис. 2 A , кривые b – d и g – i, полоса λ = 410 нм обеднена. Этот результат согласуется с тем фактом, что образующийся биокаталитически H ₂ O ₂ образует оксокомплекс с гемовым центром MP-11 в качестве промежуточного соединения, которое окисляет NADH.Последний оксокомплекс не имеет поглощения в этой области спектра (24). Таблица истинности для объединенной системы вентилей, которая работает в присутствии O ₂ (вход C = 1) с использованием трех других входов, показана на рис. С .

Рис. 2.

Работа и анализ объединенных биокаталитических ворот при наличии четырех входов.( A ) Характеристики абсорбции NADH в конкатенированной четырехферментной системе в присутствии O ₂. ( B ) Столбчатое представление выходных данных объединенных гейтов, полученных из изменений модуля поглощения. Для всех входные данные спектров соответствуют: a, поглощению биокаталитической системы до активации входами, и b – i, активации системы входами A, B, C и D, где b = 1,0, 1,1; с = 0,1,1,1; d = 1,1,1,1; е = 0,0,1,0; f = 0,0,1,1; г = 1,0,1,0; h = 0,1,1,0; и i = 1,1,1,0.Значения пороговой абсорбции 0,14 и 0,24 отмечены для всех представлений столбиков. ( C ) Таблица истинности для составных ворот при наличии O ₂. Бес, вход.

На рис. 3 изображена работа связанных вентилей при исключении O ₂ из системы (вход O ₂ всегда равен «0»). В этих условиях выход «1» логического элемента ИЛИ не приведет к формированию H ₂ O ₂, и, таким образом, выход логического элемента И всегда будет «0.Соответственно, изменения в абсорбции НАДН будут контролироваться только вводом глюкозы в вентиль XOR. Рис. 3 A , кривые b, c и d, показывают изменения оптической плотности систем во всех трех конфигурациях, где вентиль OR дает выход «1», а именно, конфигурации (1, 0, 0, 1), (0, 1, 0, 1) и (1, 1, 0, 1) соответственно. Очевидно, что для всех этих конфигураций наблюдается чистое увеличение поглощения NADH из-за некомпенсированного биоэлектрокатализируемого окисления глюкозы и образования NADH.Естественно, конфигурация системы (0, 0, 0, 1), где входы логического элемента ИЛИ равны «0», и, таким образом, выход логического элемента И также принудительно равен «0», приводит к наличию вход глюкозы «1», приводящий к чистому увеличению образования NADH (выход «1» логического элемента XOR) (рис. 3 А , кривая д). Рис. 3 B изображает выходные данные соответствующих соединенных ворот в форме представления столбцов, столбцов b, c и e. Рис. 3 A , кривые f – i, показывают характеристики абсорбции системы для всех трех объединенных гейтов, которые включают вход глюкозы «0» для логического элемента XOR.Очевидно, что для НАДН не наблюдается изменения абсорбции и, следовательно, для всех четырех конфигураций: (1, 0, 0, 0), (0, 1, 0, 0), (1, 1, 0, 0) и (0, 0, 0, 0), выход логического элемента XOR равен «0». Эти результаты представлены на рис. B , столбцы f – i соответственно. Эти результаты согласуются с тем фактом, что исключение O ₂ из системы всегда приводит к выходу «0» логического элемента AND. Поскольку в системе нет глюкозы, ни биокатализируемое окисление глюкозы, ни окисление NADH, катализируемое MP-11, не происходит, и никаких изменений в концентрации NADH не наблюдается.Следует отметить, что на всех кривых, представленных на рис. A , видна полоса поглощения MP-11 при λ = 410 нм. Этот вывод согласуется с тем фактом, что H ₂ O ₂ не образуется ни в одной из систем, и, таким образом, не образуется промежуточный оксокомплекс (24). Таблица истинности для объединенной системы вентилей, которая работает в отсутствие O ₂ (вход C = 0), с использованием трех других входов, A, B и D, показана на рис. С .

Рис. 3.

Работа и анализ нижних конкатенированных биокаталитических вентилей в отсутствие O ₂. ( A ) Характеристики абсорбции NADH в конкатенированной четырехферментной системе в отсутствие O ₂. ( B ) Столбчатое представление выходных данных объединенных гейтов, полученных из изменений модуля поглощения.Для всех спектров входные данные соответствуют: a, поглощению биокаталитической системы до активации входами и b – i, активации системы входами A, B, C и D, где b = 1,0,0 , 1; c = 0,1,0,1; d = 1,1,0,1; е = 0,0,0,1; f = 1,0,0,0; г = 0,1,0,0; h = 1,1,0,0; и i = 0,0,0,0. Значения пороговой абсорбции 0,14 и 0,24 отмечены для всех представлений столбиков. ( C ) Таблица истинности для соединенных ворот при отсутствии O ₂. Inp, input.

Следует отметить, что мы определили две области для изменений модуля абсорбции для различных сцепленных ворот.Одна область была определена как изменение модуля оптической плотности от 0 до 0,14 и считается выходным сигналом низкого уровня, который соответствует «0». Вторая область для изменений модуля поглощения была определена в диапазоне от 0,24 до 0,5 и соответствует высокоуровневому выходному сигналу или логической «1». Отметим также, что представление изменений оптической плотности в виде модуля может быть реализовано с помощью имеющихся электронных схем, которые могут быть интегрированы в анализирующий спектрофотометр. Кроме того, мы хотим подчеркнуть, что при определении областей изменения модуля поглощения для выходных сигналов ИСТИНА / ЛОЖЬ, «1» / «0» мы определили «серую» область, на которую отсутствует какой-либо определенный ответ.Эта ситуация аналогична идентификации состояний «0» / «1» в электронных компьютерах, где соответствующие области напряжения определены для логических функций. Полная таблица истинности, соответствующая работе трех объединенных биокаталитических ворот в присутствии четырех входов A, B, C и D, представлена в таблице 1.

Таблица 1.

Таблица истинности, соответствующая работе трех сцепленных вентилей на рис.1

Уникальный аспект этой системы основан на том факте, что четыре биокатализатора образуют три связанных логических элемента, которые работают последовательно. Работа интегрированной системы «считывается» выходом последних ворот. В отличие от наших предыдущих компьютерных систем на основе ферментов, где каждый биокаталитический элемент работал как отдельная единица, это исследование демонстрирует передачу информации от одного элемента к другому с помощью продуцируемых химических стимулов.Мы не рассматриваем логические вентили на основе ферментов в качестве замены электронных схем и компьютеров. Однако мы считаем, что в будущем такие системы могут найти применение в качестве «диагностических компьютеров», которые будут отслеживать биологические преобразования, такие как метаболические пути или взаимодействия лекарств. Доступность многочисленных ферментов в природе и демонстрация того, что мультиплексные биокаталитические каскады могут использоваться для создания логических операций, поддерживают наше видение будущих компьютеров на основе ферментов.

2.1. Операторы и логические операторы

ПРЕДВАРИТЕЛЬНЫЙ ПРОСМОТР \ (\ PageIndex {1} \): составные операторы

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

Конъюнкция операторов \ (P \) и \ (Q \) — это утверждение «\ (P \) и \ (Q \)», которое обозначается как \ (P \ wedge Q \). Утверждение \ (P \ wedge Q \) верно только тогда, когда оба \ (P \) и \ (Q \) верны.
Дизъюнкция операторов \ (P \) и \ (Q \) является утверждением «\ (P \) или \ (Q \)» и обозначается как \ (P \ vee Q \).Утверждение \ (P \ vee Q \) истинно только тогда, когда истинно хотя бы одно из \ (P \) или \ (Q \).
Отрицание ( утверждения ) утверждения \ (P \) является утверждением «, а не \ (P \)» и обозначается \ (\ urcorner P \). Отрицание \ (P \) истинно, только когда \ (P \) ложно, а \ (\ urcorner P \) ложно, только когда \ (P \) истинно.
Импликация или условное — это утверждение « Если \ (P \) , то \ (Q \)» и обозначается \ (P \ to Q \).Утверждение \ (P \ to Q \) часто читается как «\ (P \) подразумевает \ (Q \)», и мы видели в разделе 1.1, что \ (P \ to Q \) ложно только тогда, когда \ (P \) истинно, а \ (Q \) ложно.

Некоторые комментарии по поводу дизъюнкции.
Важно понимать использование оператора «или». В математике мы используем « включительно или », если не указано иное. Это означает, что \ (P \ vee Q \) истинно, когда оба \ (P \) и \ (Q \) истинны, а также когда истинно только одно из них.То есть \ (P \ vee Q \) истинно, если хотя бы одно из \ (P \) или \ (Q \) истинно, или \ (P \ vee Q \) ложно, только когда оба \ (P \ ) и \ (Q \) ложны.

Другое использование слова «или» — « исключающее или ». Для исключающего или результирующий оператор является ложным, если оба утверждения верны. То есть, «\ (P \) эксклюзивное или \ (Q \)» истинно только тогда, когда истинно ровно одно из \ (P \) или \ (Q \). В повседневной жизни мы часто используем эксклюзивное или. Когда кто-то говорит: «На перекрестке поверните налево или идите прямо», этот человек использует исключительное или.

Некоторые комментарии по поводу отрицания . Хотя выражение \ (\ urcorner P \) можно прочитать как «Это не тот случай, когда \ (P \)», часто есть лучшие способы сказать или написать это на английском языке. Например, мы обычно говорим (или пишем):

Утверждение «391 простое» означает «391 не простое».
Отрицание утверждения «\ (12 <9 \)» равно «\ (12 \ ge 9 \)».

Для выписок
\ (P \): 15 нечетное \ (Q \): 15 простое
запишите каждое из следующих утверждений как английские предложения и определите
, истинны они или ложны.
(а) \ (P \ клин Q \). (б) \ (P \ vee Q \). (c) \ (P \ клин \ urcorner Q \). (г) \ (\ urcorner P \ vee \ urcorner Q \).
Для выписок
P: 15 нечетное R: 15 <17
запишите каждое из следующих утверждений в символической форме, используя операторы \ (\ wedge \), \ (\ vee \) и \ (\ urcorner \)
(a) 15 \ (\ ge \) 17. (b) 15 нечетно или 15 \ (\ ge \) 17.
(c) 15 четно или 15 <17. (d) 15 нечетно и 15 \ (\ ge \) 17.

ПРЕДВАРИТЕЛЬНЫЙ ПРОСМОТР \ (\ PageIndex {2} \): истинные значения утверждений

Мы будем использовать следующие два оператора для всего этого действия предварительного просмотра:

\ (P \) — это высказывание «Идет дождь.”
\ (Q \) — это утверждение «Дейзи играет в гольф».

В каждой из следующих четырех частей утверждениям \ (P \) и \ (Q \) будет присвоено значение истинности. Например, в вопросе (1) мы предполагаем, что каждое утверждение истинно. В вопросе (2) мы будем предполагать, что \ (P \) истинно, а \ (Q \) ложно. В каждой части определите истинность каждого из следующих утверждений:

(a) (\ (P \ wedge Q \)) Идет дождь, и Дейзи играет в гольф.

(b) (\ (P \ vee Q \)) Идет дождь или Дейзи играет в гольф.

(d) (\ (\ urcorner P \)) Дождя нет.

Какие из четырех утверждений [от (a) до (d)] верны, а какие — ложны в каждой из следующих четырех ситуаций?

1. Когда \ (P \) истинно (идет дождь) и \ (Q \) истинно (Дейзи играет в гольф).
2. Когда \ (P \) истинно (идет дождь) и \ (Q \) ложно (Дейзи не играет в гольф).
3. Когда \ (P \) ложно (дождь не идет) и \ (Q \) истинно (Дейзи играет в гольф).
4. Когда \ (P \) ложно (дождь не идет) и \ (Q \) ложно (Дейзи не играет в гольф).

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

\ (П \)	\ (\ urcorner P \)
T	F
Ф	Т

\ (P \)	\ (Q \)	\ (P \ клин Q \)
T	Т	Т
Т	F	F
Ф	Т	F
Ф	F	F

\ (P \)	\ (Q \)	\ (P \ vee Q \)
T	Т	Т
Т	F	Т
Ф	Т	Т
Ф	F	F

\ (P \)	\ (Q \)	\ (от P \ к Q \)
T	Т	Т
Т	F	Ф
Ф	Т	Т
Ф	F	Т

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

Таблица 2.1: Истинные значения для общих связок
Оператор	Символическая форма	Сводка истинных ценностей
Соединение	\ (P \ клин Q \)	Верно только тогда, когда оба \ (P \) и \ (Q \) верны
Дизъюнкция	\ (P \ vee Q \)	Ложь, только если оба \ (P \) и \ (Q \) неверны
Отрицание	\ (\ urcorner P \)	Значение противоположной истинности \ (P \)
Условный	\ (P \ to Q \)	Ложь, только если \ (P \) истинно, а \ (Q \) ложно

Другие формы условных отчетов

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

Если «соблюдаются определенные условия», то «что-то происходит.”

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

Мы также должны знать, что в английском языке есть другие способы выражения условного оператора \ (P \ to Q \), кроме «Если \ (P \), то \ (Q \)». Ниже приведены некоторые распространенные способы выражения условного оператора \ (P \ to Q \) на английском языке:

Progress Check 2.1: Заявление «Только если»

Напомним, что четырехугольник — это четырехугольник.Пусть \ (S \) представляет следующее истинное условное утверждение:

Если четырехугольник квадрат, то это прямоугольник.

Запишите это условное выражение на английском языке, используя

слово «всякий раз, когда»
фраза «только если»
фраза «необходимо»
фраза «достаточно для»

Ответ: Добавьте сюда текст. Не удаляйте сначала этот текст.

Построение таблиц истины

Таблицы истинности для составных утверждений могут быть построены с использованием таблиц истинности для основных связок. Чтобы проиллюстрировать это, мы построим таблицу истинности для. \ ((P \ клин \ urcorner Q) \ к R \). Первый шаг — определить необходимое количество строк.

Для таблицы истинности с двумя разными простыми утверждениями необходимы четыре строки, поскольку существует четыре различных комбинации значений истинности для двух утверждений.Мы должны согласовываться с тем, как мы расставляем ряды. То, как мы сделаем это в этом тексте, — это пометить строки для первого оператора с помощью (T, T, F, F) и строки для второго оператора с помощью (T, F, T, F). Все таблицы истинности в тексте имеют эту схему.
Для таблицы истинности с тремя разными простыми утверждениями необходимо восемь строк, поскольку существует восемь различных комбинаций значений истинности для трех утверждений. Наша стандартная схема для этого типа таблицы истинности показана в Таблице 2.2 .

Следующим шагом является определение столбцов, которые будут использоваться. Один из способов сделать это — вернуться назад от формы данного оператора. Для \ ((P \ wedge \ urcorner Q) \ to R \) последний шаг — иметь дело с условным оператором \ ((\ to) \). Для этого нам нужно знать значения истинности \ ((P \ wedge \ urcorner Q) \) и \ (R \). Чтобы определить значения истинности для \ ((P \ wedge \ urcorner Q) \), нам нужно применить правила для оператора конъюнкции \ ((\ wedge) \), и нам нужно знать значения истинности для \ (P \ ) и \ (\ urcorner Q \).

Таблица 2.2 — это завершенная таблица истинности для \ ((P \ wedge \ urcorner Q) \ to R \) с номерами шагов, указанными внизу каждого столбца. Номера шагов соответствуют порядку заполнения столбцов.

Таблица 2.2: Таблица истинности для \ ((P \ wedge \ urcorner Q) \ to R \)
\ (П \)	\ (Q \)	\ (R \)	\ (\ urcorner Q \)	\ ((P \ клин \ urcorner Q) \)	\ ((P \ клин \ urcorner Q) \ to R \)
T	Т	Т	F	F	Т
Т	Т	F	F	F	Т
Т	F	Т	Т	Т	Т
Т	F	F	Т	Т	F
Ф	Т	Т	F	F	Т
Ф	Т	F	F	F	Т
Ф	F	Т	Т	F	Т
Ф	F	F	Т	F	Т
1	1	1	2	3	4

При заполнении столбца для \ (P \ wedge \ urcorner Q \) помните, что соединение истинно только тогда, когда оба \ (P \) и \ (\ urcorner Q \) истинны.
При заполнении столбца для \ ((P \ wedge \ urcorner Q) \ to R \) помните, что условное утверждение ложно только тогда, когда гипотеза \ ((P \ wedge \ urcorner Q) \) верна и заключение \ (R \) неверно.

Последний введенный столбец — это таблица истинности для утверждения \ ((P \ wedge \ urcorner Q) \ to R \) с использованием настройки в первых трех столбцах.

Проверка выполнения 2.2: Построение таблиц истинности

Создайте таблицу истинности для каждого из следующих утверждений:

\ (P \ клин \ urcorner Q \)
\ (\ urcorner (P \ клин Q) \)
\ (\ urcorner P \ клин \ urcorner Q \)
\ (\ urcorner P \ vee \ urcorner Q \)

Есть ли у любого из этих утверждений одна и та же таблица истинности?

Ответ: Добавьте сюда текст.Не удаляйте сначала этот текст.

Двуусловное утверждение

Некоторые математические результаты сформулированы в форме «\ (P \) тогда и только тогда, когда \ (Q \)» или «\ (P \) необходимо и достаточно для \ (Q \)». Примером может быть: «Треугольник является равносторонним тогда и только тогда, когда его три внутренних угла совпадают». Символическая форма для биконусного утверждения «\ (P \) тогда и только тогда, когда \ (Q \)» есть \ (P \ leftrightarrow Q \). Чтобы определить таблицу истинности для двусмысленного утверждения, поучительно внимательно посмотреть на форму фразы «\ (P \) тогда и только тогда, когда \ (Q \)».Слово «и» предполагает, что это утверждение является союзом. На самом деле это комбинация утверждений «\ (P \), если \ (Q \)» и «\ (P \), только если \ (Q \)». Символическая форма этого соединения — \ ([(Q \ to P) \ wedge (P \ to Q] \).

Progress Check 2.3: Таблица истинности для двухусловного утверждения

Заполните таблицу истинности для \ ([(Q \ to P) \ wedge (P \ to Q] \). Используйте следующие столбцы: \ (P \), \ (Q \), \ (Q \ to P \ ), \ (P \ to Q \) и \ ([(Q \ to P) \ wedge (P \ to Q] \). Последний столбец этой таблицы будет истинным для \ (P \ leftrightarrow Q \ ).

Ответ: Добавьте сюда текст. Не удаляйте сначала этот текст.

Другие формы двусмысленного заявления

Как и в случае с условным оператором, существует несколько распространенных способов выражения двузонального оператора \ (P \ leftrightarrow Q \) на английском языке.

Пример

\ (P \) есть и только если \ (Q \).
\ (P \) необходимо и достаточно для \ (Q \).
\ (P \) влечет \ (Q \), а \ (Q \) влечет \ (P \).

Тавтологии и противоречия

Определение: тавтология

Тавтология — это составное утверждение S, которое истинно для всех возможных комбинаций значений истинности составных утверждений, которые являются частью \ (S \). Противоречие — это составное утверждение, которое ложно для всех возможных комбинаций значений истинности составных утверждений, которые являются частью \ (S \).

То есть тавтология обязательно истинна при любых обстоятельствах, а противоречие обязательно ложно при любых обстоятельствах.

Проверка выполнения 2.4 (тавтологии и противоречия)

Для выписок \ (P \) и \ (Q \):

Используйте таблицу истинности, чтобы показать, что \ ((P \ vee \ urcorner P) \) является тавтологией.
Используйте таблицу истинности, чтобы показать, что \ ((P \ wedge \ urcorner P) \) противоречие.
Используйте таблицу истинности, чтобы определить, является ли \ (P \ to (P \ vee P) \) тавтологией, противоречием или нет.

Ответ: Добавьте сюда текст. Не удаляйте сначала этот текст.

Упражнения к разделу 2.1

Предположим, что Дейзи говорит: «Если не пойдет дождь, я буду играть в гольф». Позже в тот же день вы узнаете, что шел дождь, но Дейзи все еще играла в гольф. Было ли заявление Дейзи правдой или ложью? Поддержите свой вывод.
Предположим, что \ (P \) и \ (Q \) — утверждения, для которых верно \ (P \ to Q \) и для которых верно \ (\ urcorner Q \).Какой вывод (если таковой имеется) можно сделать об истинности каждого из следующих утверждений?
(а) \ (P \)
(b) \ (P \ клин Q \)
(c) \ (P \ vee Q \)
Предположим, что \ (P \) и \ (Q \) — утверждения, для которых \ (P \ to Q \) ложно. Какой вывод (если таковой имеется) можно сделать об истинности каждого из следующих утверждений?
(a) \ (\ urcorner P \ to Q \)
(b) \ (Q \ to P \)
(c) \ (P \ vee Q \)
Предположим, что \ (P \) и \ (Q \) — утверждения, для которых \ (Q \) ложно и \ (\ urcorner P \ to Q \) истинно (и неизвестно, если \ (R \) верно или неверно).Какой вывод (если таковой имеется) можно сделать об истинности каждого из следующих утверждений?
(a) \ (\ urcorner Q \ to P \)
(b) \ (P \)
(c) \ (P \ wedge R \)
(d) \ (R \ to \ urcorner P \)
Постройте таблицу истинности для каждого из следующих утверждений:
(a) \ (P \ to Q \)
(b) \ (Q \ to P \)
(c) \ (\ urcorner P \ to \ urcorner Q \)
(d) \ (\ urcorner Q \ to \ urcorner P \)
Есть ли у любого из этих утверждений одна и та же таблица истинности?
Постройте таблицу истинности для каждого из следующих утверждений:
(a) \ (P \ vee \ urcorner Q \)
(b) \ (\ urcorner (P \ vee Q) \)
(c) \ (\ urcorner P \ vee \ urcorner Q \)
(d) \ (\ urcorner P \ wedge \ urcorner Q \)
Имеет ли какое-либо из этих утверждений одинаковую таблицу истинности?
Постройте таблицу истинности для \ (P \ wedge (Q \ vee R) \) и \ ((P \ wedge Q) \ vee (P \ wedge R) \).Что вы наблюдаете.

Предположим, что каждое из следующих утверждений верно.

Лаура учится в седьмом классе.
— Лаура получила пятерку за тест по математике или Сара получила пятерку за тест по математике.
�� Если Сара получила пятерку на тесте по математике, значит, Лора не учится в седьмом классе.
Если возможно, определите истинность каждого из следующих утверждений. Тщательно объясните свои рассуждения.
(a) Лаура получила пятёрку за тест по математике.2 \) четное ». Выразите условный оператор \ (P \ to Q \) на английском языке, используя
(a) Форма условного оператора «if then»
(b) Слово «Implies»
(c) Форма «only if» выражения условное утверждение
(d) Фраза «необходимо для»
(e) Фраза «достаточно для»
Повторите упражнение (9) для условного оператора \ (Q \ to P \).
Для утверждений \ (P \) и \ (Q \) используйте таблицы истинности, чтобы определить, является ли каждое из следующих утверждений тавтологией, противоречием или ни тем, ни другим.
(а) \ (\ urcorner Q \ vee (P \ to Q) \).
(b) \ (Q \ клин (P \ клин \ urcorner Q) \).
(c) \ ((Q \ клин P) \ клин (P \ to \ urcorner Q) \).
(d) \ (\ urcorner Q \ to (P \ клин \ urcorner P) \).
Для утверждений \ (P \), \ (Q \) и \ (R \):
(a) Докажите, что \ ([(P \ to Q) \ wedge P] \ to Q \) является тавтологией. Примечание : В символической логике это важная форма логического аргумента, называемая modus ponens .
(b) Докажите, что \ ([(P \ to Q) \ wedge (Q \ to R)] \ to (P \ to R) \) является автологией. Примечание : В символической логике это важная форма логического аргумента, называемая силлогизмом .
Разведки и работы

Работа с условными операторами. Заполните следующую таблицу:

Английский Форма	Гипотеза	Заключение	Символическая форма
Если \ (P \), то \ (Q \)	\ (П \)	\ (Q \)	\ (P \ to Q \)
\ (Q \) только если \ (P \)	\ (Q \)	\ (П \)	\ (Q \ to P \)
\ (P \) необходимо для \ (Q \)
\ (P \) достаточно для \ (Q \)
\ (Q \) необходимо для \ (P \)
\ (P \) подразумевает \ (Q \)
\ (P \) только если \ (Q \)
\ (P \), если \ (Q \)
если \ (Q \), то \ (P \)
если \ (\ urcorner Q \), то \ (\ urcorner P \)
если \ (Q \), то \ (Q \ wedge R \)
если \ (P \ vee Q \), то \ (R \)

Работа с истинностью утверждений. Предположим, что \ (P \) и \ (Q \) — истинные утверждения, что \ (U \) и \ (V \) — ложные утверждения, и что \ (W \) — утверждение, и неизвестно, если \ (W \) истинно или ложно.
Какие из следующих утверждений верны, какие ложны и для каких утверждений невозможно определить, истинно оно или ложно? Обоснуйте свои выводы.
(a) \ ((P \ vee Q) \ vee (U \ клин W) \) (f) \ ((\ urcorner P \ vee \ urcorner U) \ клин (Q \ vee \ urcorner V) \)
(b) \ (P \ клин (Q \ к W) \) (g) \ ((P \ клин \ urcorner Q) \ клин (U \ vee W) \)
(c) \ (P \ клин ( W \ to Q) \) (h) \ ((P \ vee \ urcorner Q) \ to (U \ wedge W) \)
(d) \ (W \ to (P \ wedge U) \) (i) \ ((P \ vee W) \ to (U \ wedge W) \)
(e) \ (W \ to (P \ wedge \ urcorner U) \) (j) \ ((U \ wedge \ urcorner V) \ to (P \ клин W) \)

Ответ: Добавьте сюда текст.Не удаляйте сначала этот текст.

\ (П \)	\ (Q \)	\ (R \)	\ (\ urcorner Q \)	\ ((P \ клин \ urcorner Q) \)	\ ((P \ клин \ urcorner Q) \ to R \)
T	Т	Т	F	F	Т
Т	Т	F	F	F	Т
Т	F	Т	Т	Т	Т
Т	F	F	Т	Т	F
Ф	Т	Т	F	F	Т
Ф	Т	F	F	F	Т
Ф	F	Т	Т	F	Т
Ф	F	F	Т	F	Т
1	1	1	2	3	4

\ (П \)	\ (Q \)	\ (R \)	\ (\ urcorner Q \)	\ ((P \ клин \ urcorner Q) \)	\ ((P \ клин \ urcorner Q) \ to R \)
T	Т	Т	F	F	Т
Т	Т	F	F	F	Т
Т	F	Т	Т	Т	Т
Т	F	F	Т	Т	F
Ф	Т	Т	F	F	Т
Ф	Т	F	F	F	Т
Ф	F	Т	Т	F	Т
Ф	F	F	Т	F	Т
1	1	1	2	3	4

Логические операции и таблицы истинности

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

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

Для самостоятельного выполнения

Контрольная работа по теме «Основы логики» 9 класс

Открытый урок на тему:»Логические операции» (10 класс) | Методическая разработка по информатике и икт (10 класс):

глава 3. Онлайн-тесты для 10 класса

Контрольная работа по информатике на тему: Алгебра логики. Таблицы истинности.

L04: Комбинационная логика

L04: Комбинационная логика

из AMS

Введение: Исчисление логических функций

Таблицы истинности

Таблицы истинности и диаграммы

Диаграммы Венна для более чем трех операторов

Топологически точные диаграммы Венна в более высоких измерениях

Приложение

Введение в цифровую логику — Глава книги

Цзюньхуа Чен

Цзяфэн Пан

Шу Чен

Abstract

Введение

Результаты и обсуждение

Выводы

Заявление о живом испытуемом

Конфликт интересов

Дополнительные материалы

Благодарности

Ссылки

Логические ворота NAND, NOR и XOR — видео и стенограмма урока

Логические вентили И-НЕ, ИЛИ-ИЛИ и ИСКЛЮЧАЮЩЕЕ ИЛИ

Функциональная полнота

Итоги урока

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

Результаты и обсуждения

2.1. Операторы и логические операторы

Другие формы условных отчетов

Построение таблиц истины

Двуусловное утверждение

Другие формы двусмысленного заявления

alexxlab

Добавить комментарий Отменить ответ

Рубрики

\ (П \)	\ (Q \)	\ (R \)	\ (\ urcorner Q \)	\ ((P \ клин \ urcorner Q) \)	\ ((P \ клин \ urcorner Q) \ to R \)
T	Т	Т	F	F	Т
Т	Т	F	F	F	Т
Т	F	Т	Т	Т	Т
Т	F	F	Т	Т	F
Ф	Т	Т	F	F	Т
Ф	Т	F	F	F	Т
Ф	F	Т	Т	F	Т
Ф	F	F	Т	F	Т
1	1	1	2	3	4