3 и не таблица истинности: Таблицы истинности логических функций

Таблицы истинности логических функций

⇐ ПредыдущаяСтр 15 из 19Следующая ⇒

x1 x2	f1	f2	f3	f4	f5	f6	f7
		Λ	V	~	→	↓	|	⊕

 

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

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

Равнозначность

Импликация

Функция Вебба (стрелка Пирса, ИЛИ-НЕ)

Функция Шеффера (И-НЕ)

Функция сложения по модулю два (полусумматор)

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

 

Можно условиться, что разомкнутый ключ эквивалентен логическому нулю, а замк­нутый –логической единице. Таким обра­зом, ключ реализует переменную х, если он замкнут при х = 1, и переменную , ес­ли он разомкнут при х = 1.

Рассмотрим сначала, какая логическая функция будет реализована, если два клю­ча и соединить последовательно.

 

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

Функция ИЛИ может быть получе­на, если ключи включить параллельно.

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

Рассмотрим это на примере правила повторения.

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

 

Другой возможностью представления логических переменных является электри­ческое напряжение, имеющее два раз­личных уровня: высокий и низкий. Этим уровням можно поставить в соответствие логи­ческие состояния 1 и 0. Эта система обо­значений: высокий = 1 и низкий = 0 – на­зывается позитивной логикой. Но возмож­на также и обратная система обозначений: высокий = 0 и низкий = 1, которая назы­вается негативной логикой.

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

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

 

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

дизъюнктивной совершенной нормальной форме (ДСНФ). При этом поступают следующим образом.

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

2. Для каждой такой строки составляют конъюнкцию всех входных переменно причем записывают сомножитель , если рассматриваемая переменная принимает значение 1, в противном случае записывают . Таким образом, составляется столько произведений, сколько имеется строк с у = 1.

3. Наконец, записывая логическую сумму всех найденных произведений, получают искомую функцию.

 

Формулы склеивания:

Формулы поглощения:

 

Минимизация методом Карно

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

Желательно образовывать контуры возможно большей протяженности. Контуры могут охватывать 1, 2, 4,8 и т. д. единиц (или нулей). В результате исчезает та переменная, которая меняет знак при обходе контура. При организации контуров следует считать, что карту можно навернуть на цилиндр.

Если обхватывать контурами единицы, то результат получим в ДСНФ, если нули – то в КСНФ (конъюнктивная совершенная нормальная форма).

	f

2-х разрядная карта Карно

 

Результат:

 

Элементарная база цифровых микросхем. Логические элементы И, ИЛИ, НЕ на диодах, биполярных и полевых транзисторах. Базовые логические элементы диодно-транзисторной, транзисторно-транзисторной, эмиттерно-связанной логики. Логические элементы на однотипных и комплементарных МДП-транзисторах. Логические элементы с тремя выходными состояниями. Микросхемы с открытым коллектором. Совместное применение микросхем разных серий.

 

 

Эволюция цифровой логики:

1) РТЛ – резисторно-транзисторная логика.

2) ДТЛ – диодно-транзисторная логика.

3) ТТЛ –транзисторно-транзисторная логика.

Элемент три «И-НЕ» на ДТЛ.

Напряжение <0.4B считается логическим нулем, при U>2.4 – логическая единица.

Элементы на основе ТТЛ.

В основе – многоэммитерный транзистор.

Серия 155.

Если на всех входах «1» , то на коллекторе эмиттерный переход закрыт, а коллекторный открыт и напряжение на базе VT1=1.

8 В. VT2 и VT5 открыты, VD4 –предназначен для надежного запирания VT4. R3, R4 и VT3 действуют как резистор и предназначены для увеличения помехоустойчивости.

Если на любом из входов «0», то VT1 переключается из инверсного в активный режим и отпирается. В этом случае напряжение на его коллекторе (0,8В) уже недостаточно для отпирания VT4 и VT5. VT4 при этом открыт и на выходе появляется логическая единица.

R5 предназначен для защиты выходов при кратковременном замыкании на землю.

 

 

Серия повышенного быстродействия.

VT1, VT2 – VT5 – используются транзисторы Шотке.

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

 

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

У диода Шотке напряжение отпирания 0,3-0,4 В. Напряжение на базе транзистора Шотке не может превышать напряжение на его коллекторе более, чем на 0,4 В, т.

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

 

Читайте также:

 

ЕГЭ по информатике — Задание 2 (Мощнейший метод)

Здравствуйте, дорогие друзья! Сегодня разберём, как решать второе задание из ЕГЭ по информатике 2020.

Во втором задании ЕГЭ по информатике у нас обычно есть логическая функция, которая зависит от логических переменных. Логические переменные могут принимать только два значения: 0 (Ложь) или 1 (Истина).

С логическими переменными можно производить логические операции. При решении второго задания из ЕГЭ по информатике необходимо твёрдо знать каждую

логическую операцию, и давайте рассмотрим их.

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

1. () — операции в скобках
2. ¬ — логическое отрицание
3. ∧ — логическое умножение
4. ∨ — логическое сложение
5. ⟶ — следование
6. ≡ — равнозначность

Так же на ЕГЭ по информатике будет полезно знать логические формулы :
Ещё соотношения:

Передём к решению задач из ЕГЭ по информатике

Задача 1 (лёгкая)

Логическая функция F задаётся выражением z ∧ ¬y ∧ (w → x). Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F. Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z, w.

В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно. Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:

Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.

Решение:

Видим, что у функции основным действием является логическое умножение. По таблице видно, что функция имеет значение только 1 . Логическое умножение даёт 1 (единицу) тогда, когда каждое выражение равно 1 (единице). Значит каждое выражение в нашей функции должно равняться единице.

Отсюда видно, что переменная z должна всегда быть равна 1 (единице). Это первый столбец. Отрицание y тоже должно быть 1 (единицей), тогда просто y всегда будет 0 (нулём). Это второй столбец.

Осталось определить положение w и x. Здесь делаем предположение, что в третьем столбце стоит w, а в 4-ом x. Проверяем построчно и видим, что во второй строчке при таком расположении из 1 следует 0, что в итоге приводит выражение (w → x) в 0, а у нас это выражение всегда должно быть 1 (единицей). Значит, мы предположение сделали неверное, и получается x — это третий столбец, а w — четвёртый.

Ответ: zyxw

Задача 2 (средний уровень)

Логическая функция F задаётся выражением (x ∧ ¬y) ∨ (y ≡ z) ∨ w.
Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F. Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z, w.

В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:

Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.

Решение:

Определяем главную логическую операцию («главную скрипку»), которая соединяет разные выражения. Видим, что это логическое сложение.

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

Самым слабым звеном является переменная w, потому что она стоит одна. Переменная w должна равняться всегда 0(нулю) — этому условию может удовлетворить только третий столбец. Значит w стоит на третьем месте.

Следующим слабым звеном является равносильность. Она должна «выдавать» 0 (ноль). Равносильность «выдаёт» 0 (ноль), когда переменные разные!

Проанализируем первый и второй столбец. В третьей строчке, и там, и там, стоит 1 (единица). Значит, первый и второй столбец не могут быть одновременно y и z (или z и y).

Рассмотрим второй и четвёртый столбец. Вторая строчка содержит одинаковое значение 0 (ноль), и там, и там. Значит, второй и четвёртый столбец не могут быть одновременно y и z (или z и y).

Таким образом, y и z (или z и y) будут столбцы первый и четвёртый! И теперь можно расставить недостающие значения в этих столбцах. Расставляем, чтобы были разные значения, а второй столбец получается x.

Осталось разобраться с z и y. Обратимся к первому выражению (x ∧ ¬y) и посмотрим на третью строчку. Если в четвёртом столбце будет стоять y, то отрицание на y превратит ноль(ноль) в 1(единицу) в четвёртой строчке. Тогда окажется, что у x — 1 и ¬y — 1, и выражение (x ∧ ¬y) тоже получится 1(единицей). А у нас каждое выражение должно равняться 0(нулю). Получается y будет стоять в первом столбце, а z в четвёртом.

Тогда ответ будет равен yxwz.

Ответ: yxwz

Мощнейший метод для решения второго задания из ЕГЭ по информатике

Задача 3 (хороший уровень)
Логическая функция F задаётся выражением ((x → y ) ∧ (y → w)) ∨ (z ≡ ( x ∨ y)).
Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F. Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z, w.
В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:

Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.

Решение:

«Главной скрипкой» в нашей функции является логическое сложение, потому что соединяет два выражения ((x → y ) ∧ (y → w)) и (z ≡ ( x ∨ y)).

Тогда каждое выражение должно равняться 0(нулю).

Теперь кульминация мощнейшего метода. У нас всего 4 переменных. Выпишем все комбинации для 4-х переменных. Таблица будет точно такая же, как мы писали в первом задании (её очень легко составить). Всего получается 16 комбинаций (16 = 2⁴).

Теперь отметим зелёным плюсом те строчки, которые обращают выражение ((x → y ) ∧ (y → w)) в 0(ноль). Следующий шаг: Отметим галочкой те строчки, которые обращают в ноль второе выражение (z ≡ ( x ∨ y)) (Мы должны искать среди тех, которые уже отмечены плюсом).

При небольшой тренировке анализ подобных выражений занимает сущие секунды!

У нас получается 4 строчки, которые удовлетворяют нашей функции:

Отсюда видно, что переменная z может быть равна только 0(нулю)! Значит, она занимает третий столбец, потому что в остальных столбцах есть хотя бы одна 1(единица).

Переменная w имеет только одну 1(единицу). Значит, её ставим во второй столбец, потому что в первом и четвёртом уже по 2 единицы минимум, а третий уже занят z.

Теперь находим строчку c 1(единицей) в переменной w (Таблица данная в условии задачи) Кто в этой строчке будет иметь единицу (кроме w) — будет x! Это четвёртый столбец! Значит, x — это четвёртый столбец. Переменной y — достаётся первый столбец

Ответ: ywzx.

На этом всё! Сегодня рассмотрели теорию и основные методы для эффективного решения второго задания из ЕГЭ по информатике!

Пока!
[/ youtube]

У этого есть имя, которое вы также должны знать:

(стр.	>	к)	/ кв	// п.
т	Т	Т	Т	Т
т	F	F	F	Т
Ф	Т	Т	Т	F
Ф	Т	F	F	F

Недействительность здесь также показана в третьей строке, где обе посылки — T, а заключение — F. Первая строка, в которой и посылки, и заключение являются T, не указывает ничего, что могло бы противодействовать тому, что показывает третья строка, а именно, что эта форма допускает возможность T посылок и F вывода.

Это Подтверждающее Следствие .

Вот еще один вариант:

~	(G	∙	М)	/ M	v	~ G	// ~ G
Ф	Т	Т	Т	Т	т	F	F
т	Т	F	F	F	Ф	F	F
т	F	F	Т	т	т	Т	т
т	F	F	F	F	т	Т	т

В помещении сказано: «Не одновременно G и M. Либо M, либо G ложны ». Вывод: «Не Г.».

Это может быть

Неверно, что и Гарфилд, и Мармадьюк — собаки. Либо Мармадьюк собака, либо не Гарфилд. Следовательно, Гарфилд не один.

Что показывает таблица? Это показывает, что всякий раз, когда вывод — F, по крайней мере, одна посылка тоже F. В первой и второй строках вывод — F. Но в первой строке первая посылка — это F (смотрите под знаком ~), а во второй строке вторая посылка — F (смотрите под v).Это показывает, что он не недействителен, следовательно, действителен.

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

8 Таблицы истинности аргументов

Вот несколько упражнений, над которыми вы можете практиковаться:

1. P ≡ ~ N // N v P

2. K ≡ ~ L / ~ (L ∙ ~ K) // K> L

3. Z // E> (Z> E)

4. C ≡ D / E v ~ D // E> C

5. A> (B v C) / ~ C v B // A> B

6. J> (K> L) / K> (J> L) // (J v K)> L

7. Если Сартр экзистенциалист, то Витгенштейн написал Трактат, следовательно, если Витгенштейн написал Трактат, Сартр экзистенциалист.

8. Херли — президент, так что либо он президент, либо Аккерманн — декан.

9.Если «время летит» — это метафора, это не совсем так. Если это не совсем так, тогда время не летит, поэтому, если «время летит» — метафора, то время не летит.

10. Если аргумент от дизайна слабый, это слабая аналогия. Чтобы быть слабой аналогией, оно должно проводить неоправданное сравнение, поэтому аргумент, исходящий от дизайна, дает неоправданное сравнение.

11. Зима холодная, а лето жаркое, поэтому либо лето жаркое, либо луна сделана из зеленого сыра.

12.Рассел был либо реалистом, либо эмпириком. Если первое, то он не был идеалистом, значит, он не был эмпириком.

13. Если он любит ее, он женится на ней. Поэтому, если он ее не любит, он не женится на ней.

14. Если люди смогут поселиться на Луне, они смогут поселиться на Марсе. Если они смогут поселиться на Марсе, они смогут поселиться на Юпитере. Итак, если Луна может быть заселена, то и Юпитер может.

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

16. Тот факт, что животные менее умны, чем мы, не означает, что мы можем пренебрегать их благополучием. Если мы пренебрегаем их благополучием, тогда мы бесчеловечны и ничем не лучше самих животных. Таким образом, если мы пренебрегаем их благополучием, будет ошибкой считать, что они менее умны, чем мы.

17. Если Швеция находится в Северной Африке, то либо египтяне голубоглазые, либо шведы смуглые и красивые. Швеция находится не в Северной Африке, поэтому египтяне не голубоглазые.