Алгебра логики: Построение таблиц истинности
Алгоритм построения таблицы истинности
- Определить число переменных
- Определить число строк в таблице истинности
- Записать все возможные значения переменных
- Определить количество логических операций и их порядок
- Записать логические операции в таблицу истинности и определить для каждой значение
Определение количества строк и столбцов в таблице истинности.
Т.к. каждое из простых высказываний может принимать всего два значения (0 или 1), то количество разных комбинаций значений n высказываний – 2 n .
Количество строк в таблице = 2 n + строка на заголовок.
Количество столбцов в таблице равно сумме количества
простых высказываний (n) и количества
разных логических операций, входящих в сложное высказывание.
В нашем примере: количество строк — 22 + 1 = 5 ,
столбцов – 2 + 4 = 6
Согласно определению, таблица истинности логической формулы выражает соответствие между всевозможными наборами значений переменных и значениями формулы.
Для формулы, которая содержит две переменные, таких наборов значений переменных всего четыре: (0,0), (0,1), (1,0), (1,1).
Если формула содержит три переменные, то возможных наборов значений переменных восемь:
(0,0,0), (0,0,1), (0,1,0), (0,1,1),
(1,0,0), (1,0,1), (1,1,0), (1,1,1).
Количество наборов для формулы с четырьмя переменными равно шестнадцати и т.д.
Удобной формой записи при нахождении значений формулы является таблица, содержащая кроме значений переменных и значений формулы также и значения промежуточных формул.
Примеры.
1. Составим таблицу истинности для
формулы , которая содержит две переменные
x и y. В первых двух столбцах таблицы запишем четыре возможных пары значений
этих переменных, в последующих столбцах — значения промежуточных формул и в
последнем столбце — значение формулы. В результате получим
таблицу:
1) , 2) , 3) , 4) , 5)
Переменные | Промежуточные логические формулы | Формула | |||||
| X | Y | ||||||
1 | 1 | 1 | 1 | ||||
1 | 1 | 1 | 1 | 1 | 1 | ||
1 | 1 | 1 | |||||
1 | 1 | 1 | 1 | ||||
Из таблицы
видно, что при всех наборах значений переменных x и y формула принимает значение 1, то есть
является тождественно истинной.
«Алгебра логики». Использование мобильных приложений на уроке информатики
Дисциплина: Информатика.
Цели урока:
Образовательные:
- закрепить знания учащихся по теме «Алгебра логики: основные законы алгебры логики»;
- дать учащимся представление о подходах к пониманию алгебры высказываний;
Воспитательные:
- воспитание самостоятельности, коммуникабельности, формирование понимания значения логики в современном информационном мире;
- сочетание индивидуальной и коллективной работы;
- ответственность за выполнение домашнего задания;
Развивающие:
- развитие познавательного интереса учащихся;
- памяти; внимания; развитие способности применять усвоенные теоретические знания в практической работе;
- развить логическое мышление;
- сформировать практические умения решать логические задачи.
Тип урока: Комбинированный урок.
Межпредметные связи: математика.
Оборудование урока: ПК, мультимедийное оборудование, презентация к уроку на тему «Алгебра логики: таблицы истинности и основные законы алгебры логики», раздаточный материал – карточки с заданиями, электронные таблицы Microsoft Excel, мобильное приложение «Сканер» и «Logic Calculator».
Ход урока
I. Теоретический этапДоброе утро, ребята! На прошлых уроках мы изучили тему «Алгебра логики», на которых познакомились с определениями логика и логическое высказывание и основными логическими операциями, которые задаются таблицами истинности. А также узнали, что в алгебре логики имеется ряд законов, позволяющих производить равносильные преобразования логических выражений. Давайте вспомним и повторим материал прошлых уроков? (Повторение пройдённого материала по предыдущей теме проводится в виде кроссворда, вопросы которого зашифрованы в QR-кодах и распечатаны на карточках (Приложение 1, Приложение 2, Приложение 3), для расшифровки, которых необходимо воспользоваться смартфоном с установленным приложением «Сканер QR-кодов». Кроссворд также выведен на экран (Слайд 2)).
Интерактивная беседа сопровождается презентацией, содержащей теоретическое описание и иллюстративное отображение изучаемой темы, каждый элемент которых является обобщением или подтверждением некоторого этапа обсуждения, отдельных элементов выполнения решения, обучающихся под руководством преподавателя.
2. Постановка цели и задач урокаСкажите, пожалуйста, для чего нужна логика? Связана ли алгебра логики с появлением первого персонального компьютера? (Студенты должны ответить)
Поначалу алгебра логики не имела никакого практического значения. Однако уже в XX веке ее положения нашли применение в описании функционирования и разработке различных электронных схем. Законы и аппарат алгебры логики стал использоваться при проектировании различных частей компьютеров (память, процессор). Хотя это не единственная сфера применения данной науки.
Во-первых, для получения представления об устройстве компьютера необходимо познакомиться с основными логическими элементами, лежащими в основе его построения. Теперь мы можем сформулировать цель нашего урока: (Для понимания принципа работы таких элементов нужно изучить основные начальные понятия алгебры логики).
Во-вторых, важной составляющей алгоритмов являются логические условия. Вычисление и построение, которых осуществляется в соответствии с законами алгебры логики.
В-третьих, человек с древних времен стремился познать законы правильного мышления, т. е. логические законы. Законы развития есть у природы, общества, любой сложной системы и, конечно же, у самого мышления. Существует даже мнение, что всякое движение нашей мысли, постигающей истину, добро и красоту, опирается на логические законы. Познание истины – одна из важнейших потребностей человека. Каждый человек и человечество в целом стремятся к истине, добру и красоте. Все люди нуждаются в истинном знании, получении новой информации о мире, в котором они живут. Для чего? Для того, чтобы жить, что в данном случае означает ориентироваться в быстро меняющейся обстановке, принимать правильные решения и на их основе совершать правильные действия.
Таким образом, сегодня на уроке мы вспомним понятия основных логических операций и закрепим эти понятия на основе построения таблиц истинности по логическим выражениям с использованием компьютера и мобильного приложения.
3. Объяснение теоретического материалаВ кроссворде мы с вами встретили два имени знаменитых математиков и логиков, которые внесли большой вклад в развитие математической логики. Сейчас я расскажу о них подробнее.
(Слайд 4) Джордж Буль (англ. George Boole; 2 ноября 1815 – 8 декабря 1864) – английский математик и логик. Профессор математики Королевского колледжа Корка с 1849 года. Один из основателей математической логики.
Джордж Буль родился и вырос в семье небогатого ремесленника Джона Буля, увлечённого наукой. Отец, интересуясь математикой и логикой, дал первые уроки своему сыну, но тот не сумел рано обнаружить свои выдающиеся таланты в точных науках, и его первым увлечением стали классические авторы.
Лишь к семнадцати годам Буль дошёл до высшей математики, продвигаясь медленно из-за отсутствия действенной помощи.
С шестнадцати лет Буль начал работать помощником учителя в частной школе в Донкастере и, так или иначе, продолжал преподавание на разных должностях в течение всей жизни. Он был женат (с 1855 г.) на Мэри Эверест (з. Эверест-Буль), племяннице знаменитого географа Джорджа Эвереста, также занимавшейся наукой и преподаванием, а после смерти мужа много сил уделившей популяризации его вклада в логику.
Четыре их дочери снискали известность как учёные (геометр Алисия, химик Люси), или члены учёных семей (Мэри, жена математика и писателя Ч.Г.Хинтона, и Маргарет, мать математика Дж. И. Тейлора), а пятая – Этель Лилиан Войнич – прославилась как писатель.
Буль умер на пятидесятом году жизни от воспаления лёгких.
Огастес (Август) де Мо́рган (англ. Augustus de Morgan, 27 июня 1806 – 8 марта 1871) – шотландский математик и логик, профессор математики в Университетском колледже Лондона. Первый президент (1866) Лондонского математического общества.
Основные труды: по математической логике и теории рядов; к своим идеям в алгебре логики Огастес де Мо́рган пришёл независимо от Дж. Буля. В 1847 изложил элементы логики высказываний и логики классов, дал первую развитую систему алгебры отношений. С его именем связаны известные теоретико-множественные соотношения (законы де Моргана).
Законы де Мо́ргана (законы общей инверсии для логического сложения и для логического умножения) – логические правила, связывающие пары логических операций при помощи логического отрицания. И звучат так:
(Слайд 5-6) Общая инверсия двух логических слагаемых равносильна логическому умножению инвертированных переменных:
(A ˅ B) = A &B
Общая инверсия двух логических сомножителей равносильна логическому сложению инвертированных переменных:
(A & B) = A ˅B
Диаграммы Венна, описывающие законы де Моргана представлены на рисунках 1 и 2:
II. Практический этап Практическое задание №1В электронных таблицах доказать справедливость первого (A ˅ B) = A &B и второго (A & B) = A ˅ B законов де Моргана (Слайд 7), используя таблицы истинности (рис.3).
Рис.3
Далее студентам необходимо воспользоваться мобильным приложением Logic Calculator и доказать справедливость первого (A ˅ B) = A &B и второго (A & B) = A ˅ B законов де Моргана, используя приложение Logic Calculator.
1. (A ˅ B) = A &B
2. (A & B) = A ˅ B
Практическое задание №2
В мобильном приложении Logic Calculator построить таблицу истинности логического выражения: (A ˅ B) & (A ˅ B). Ответ записать в тетради.
В мобильном приложении Logic Calculator построить таблицу истинности логического выражения: A & (B ˅ B &C). Ответ записать в тетради.
III. Заключительный этап
- Сообщение о достижении целей урока.
- Оценка работы обучающихся, комментарии.
- Выдача домашнего задания. (Доказать с использованием приложения Logic Calculator равносильность выражений (A ˅ B ˅ C) & (A ˅ B ˅ C) и (B &A & C)
Булева алгебра с использованием справочных таблиц (LUT)
Перейти к содержимому Урок 4: Что такое справочная таблица (LUT)? В предыдущей статье мы обсудили основы булевой алгебры, а именно, как работают вентили И, ИЛИ, НЕ, исключающее ИЛИ и И-НЕ. Обсуждалась концепция таблиц истинности . На этой странице мы расширим тему работы таблиц истинности и обсудим более сложные уравнения булевой алгебры.
Во-первых, следует отметить, что все те дискретные логические элементы, которые мы обсуждали ранее (И, ИЛИ и т. д.), на самом деле делают , а не физически существуют внутри ПЛИС! Однако эти функции можно выполнять. Способ, которым FPGA могут выполнять булевую алгебру, заключается в использовании справочных таблиц (LUT) . Справочная таблица — это отдельный блок функций, который может быть запрограммирован в программе Digital Designer. LUT используют ту же концепцию таблицы истинности, чтобы связать выходные данные с входными данными. Давайте попробуем пример.
Создайте таблицу истинности для следующего логического уравнения: Q = A*B + A’. Возможно, нам следует определить, что означают эти символы. 9= XOR
Таким образом, логическое уравнение Q = A*B + A’ можно прочитать так: «Выход Q получает A и B или не A». (количество входов). Давайте теперь рассмотрим еще один пример с тремя входами. Вот уравнение, для которого мы собираемся создать таблицу истинности: Q = A + (C*B’). Обратите внимание, что круглые скобки указывают на то, что операция C AND NOT B выполняется до операции OR.
| Таблица истинности – A + (C*B’) | |||
|---|---|---|---|
| Вход А | Вход Б | Вход С | Выход Q |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Как упоминалось в начале этой статьи, внутри FPGA фактически не существует дискретных логических элементов.
LUT могут быть разных размеров в зависимости от используемой FPGA, но все они ведут себя одинаково. Не так давно 3-входовые LUT были нормой, но сегодня распространены 4-входовые и даже 5-входовые LUT. Если вам нужно составить более сложное выражение, вы можете просто использовать больше справочных таблиц. LUT являются одним из двух наиболее фундаментальных компонентов FPGA. Одна ПЛИС содержит тысячи таких компонентов. Теперь, когда вы лучше знакомы с этими удивительно универсальными компонентами, пришло время обсудить другой наиболее важный элемент внутри FPGA:
The Flip-Flop (AKA Register)
Примечание для читателя: во многих учебниках и аудиториях будет уделено значительное количество времени обсуждению того, как можно подключить LUT для создания оптимального решения логического выражения.
ПЛИС-101
Рассел2022-06-30T19:42:10+00:00Перейти к началу
содержание:
Особенности Выбор меню Установка Формула Ввод Операции Таблица Ввод Выходные данные Правила сокращения CNF — DNF Недоценс Tautology Save & Load Перевод информации SCAN. Введение Logic10 — это программа, которая:
. 2. Сокращает таблицы истинности, применяя правила булевой алгебры. Щелкните [ ЗДЕСЬ ] для программирования сокращения таблицы истинности. Logic10 отлично помогает в изучении булевой алгебры, проектировании цифровых электронных схем Это Logic10 версии 2.0 Так выглядит Logic10 в работе:(уменьшенное изображение)
ввод и редактирование формул и таблиц истинности 2. вывод (сокращенных) таблиц истинности 3. информация о процессе перевода или сокращения формулы Характеристики Особенности Logic10:
— вывод : Таблица истинности в формате CNF или DNF — сохранить и перезагрузить всех входных и выходных данных — печать входных данных и выходных результатов — по выбору: информация о процессе перевода формулы — по выбору: пошаговая информация о процессе восстановления — В линии помощь информация Пункты меню см. ниже:Изображения слева направо позволяют
— сохранение таблицы истинности и настроек на диск — распечатать ввод и таблицу истинности — настройка принтера — отображать справочную информацию 902:30
В верхней части окна вывода можно выбрать выход CNF или DNF. Кроме того, флажок может быть установлен, если необходимо уменьшить таблицу истинности. В верхней части поля Информация можно отметить два флажка: Установка Logic10 написан для Windows. Язык программирования — Delphi. 902:30 Загрузите Logic10, щелкнув значок загрузки (молния) в верхней части этой страницы.Нет никакой процедуры установки, просто скопируйте Logic10 в папку по выбору. Реестр Windows не изменен. Ввод формулы ниже подробное изображение поля ввода формулы:Логические переменные представляют собой одиночные символы A..Z 902:30 Допускается выбор не более 15 различных символов. Круглые скобки (…) могут использоваться на 20 уровнях для определения приоритета операций. Операторы с их приоритетом
Примечания: 1. между переменными «.» Оператор И может быть опущен. Программа добавляет «.» автоматически. 902:30
2. то же самое между переменной и «(» или «) и переменной » ввод оператора: ABC = ABC А(В+С) = А.(В+С) (А+В)(С+D) + (А+В).(С+D) Примечание: Осторожно: При продолжении формулы на следующей строке символ «.» оператор вставляется между последовательными переменными, поэтому эта формула А+Б С+ГИнтерпретируется как: A+B.C + D Чтобы удалить строку, введите ctrl y Операции В таблице ниже перечислены таблицы истинности для всех операций.
Ввод таблицы истинности Входными данными может быть таблица истинности не более 100 строк. Начните вводить имя переменной (A..Z) в верхней части таблицы. Входная таблица находится в форме CNF, поэтому каждая строка представляет собой операцию И своих переменных, строки объединяются по схеме ИЛИ. 902:30 Введите «0», если отрицательная переменная должна быть истинной, введите «1», если переменная должна быть истинной. Итак, эта таблица
А Б В Г
0 1 1
1 1 0
Представляет формулу: /A C D + A B /DВыход таблицы истинности При нажатии кнопки GO формула транслируется в список основных операций в порядке их приоритета.Затем запускается счетчик для генерации всех возможных состояний 0,1 переменных и выполняются операции. 902:30 Для режима CNF: если окончательный результат дает true, значения переменных добавляются в выходную таблицу истинности. Для режима DNF:
если результат ложный, то значения переменных копируются в выходную таблицу истинности. Правила сокращения Если установлен флажок уменьшить , то для уменьшения выходной таблицы применяются правила логической алгебры. 902:30 Нет никакой разницы между режимами CNF и DNF.В этом процессе сокращения используются следующие правила:
2…..А + АВ =А 3…..А/В + АВ = А 4…..А + /АВ = А + В 5…..A /B + BC —> AC Обратите внимание, что такая формула, как A + A, представляет структуру 90 230
он может отображаться как D/F + D/F или как PQ/(X+Y+Z) + PQ/(X+Y+Z) Правило 5. Основное изменение по сравнению с предыдущим уровнем 1.2 Оно заменяет старые правила 5. и 6. и устраняет все известные «утечки» в процессе редукции. В правиле 5. AC называется виртуальным термином и лишь временно добавляется в процесс сокращения. Правило 5. означает, что если AC =1, то A/B + BC = 1, однако обратное неверно. Правила сокращения для виртуальных терминов такие же, как и для обычных терминов, за одним исключением:
Сам термин удаляется из окончательной таблицы истинности. Добавление термина без родителей изменит формулу. Виртуальный и обычный термин из таблицы истинности могут быть объединены (по ИЛИ), что может привести к
— уменьшение виртуального срока — сокращение или удаление члена таблицы истинности Виртуальные термины, происходящие от других виртуальных терминов, также имеют более двух родителей. Родителями являются все термины, которые внесли свой вклад в виртуальный термин путем редукции или генерации. Вход таблицы истинности При нажатии GO входная таблица истинности копируется в выходную таблицу.Если отмечено , уменьшить , то таблица будет сокращена по приведенным выше правилам 1..5. КНФ и ДНФ Выходная таблица истинности может быть в форме CNF или DNF.CNF означает «конъюнктивную нормальную форму», которая представляет собой ABC + DEF + GHI + ….. . Итак, И отдельных переменных (с предшествующим / или без него), которые объединяются по ИЛИ. ДНФ означает «дизъюнктивную нормальную форму», которая представляет собой (A+B+C)(D+E+F)(G+H+I)(…. 902:30 Итак, ИЛИ отдельных переменных (с предшествующим / или без него), которые объединены И. В режиме DNF при формировании выходной таблицы истинности Logic10 вводит значения переменных в таблицу для значений Примечание: cnf………AB + BC = (A+C)(A+D)(B+C)(B+D)………dnf 902:30 Это прямое следствие второго закона распределения. (см. учебник по булевой алгебре) Также законы де Моргана иллюстрируют связь между КНФ и ДНФ. Несоответствие Логическая формула (предложение) несостоятельна, если она никогда не приводит к истине.Простое несоответствие: ……A./A Logic10 сообщает о несоответствиях. Тавтология Логическая формула (предложение) называется тавтологией, если она всегда истинна. 902:30 Простая тавтология:……..A + /ALogic10 сообщает о тавтологиях. Сохранить и загрузить При нажатии на значок сохранения (дисковая пластина) открывается диалоговое окно для выбора имени файла.Logic10 не использует расширения имен файлов, так как их и так достаточно. Однако для ясности выбранное имя файла имеет префикс logic10_ (если это еще не сделано). Все данные: входная формула, входная таблица CNF и выходная таблица истинности сохраняются в одном файле. Чтобы перезагрузить сохраненные данные, щелкните значок карты и выберите файл. Перевод информации если xlate флажок установлен, информация о переводе формулы отображается в информационном поле.ниже подробная картинка Добавляется третий столбец с приоритетом операции. Из этой таблицы составляется таблица переменных . Правильный директор стол является окончательным результатом перевода.
2. регистр назначения 3. исходный операнд1, регистр 4. регистр исходного операнда2 При установке определенных значений переменных и выполнении таблицы директоров формула оценивается как true или false . Информация о сканировании Просмотр таблицы истинности сводится к сравнению ( ИЛИ ing) каждой строки (term) и ed переменных с каждым другим термином.Индексами таблицы истинности являются [i] и [j]. Итак, запись таблицы истинности [i] сравнивается с записью [j]. Анализ пары терминов дает 4 логических результата: привет Отверстие-яЭто верно, когда [ i ] удалил переменные, которые присутствуют в [ j ]
А Б В Г Д Е
[i] 0 0 х 0 х х
[к] 1 0 х 1 1 0
В приведенной выше таблице переменные E, F исключаются в [ i ], но не в j, поэтому hi верно.хдж Отверстие-jЭто верно, когда [ j ] удалил переменные, которые присутствуют в [ i ]
А Б В Г Д Е
[i] 1 х 1 1 0 0
[j] 0 х 0 х х х
Здесь [ j ] удалил переменные D, E, F, которые не удалены в [ i ], поэтому hj истинно.сб Один бит означает, что разница (исключающее или) между [ i ] и [ j ] имеет только 1 бит.
А Б В Г Д Е
[i] х 1 1 1 0 1
[к] 0 х 1 1 1 1
Отличаются только биты E. Столбцы, имеющие x (удаленная переменная), игнорируются. Итак, сб верно. зб Нулевой результат, также называемый равным или без разницы
А Б В Г Д Е
[i] 0 1 1 1 х 0
[к] 0 1 х 1 1 0
Столбцы с x игнорируются. Остальные столбцы должны быть равны. Итак, ЗБ верно. hi(3) hj(2) sb(1) zb(0) — биты 3,2,1,0 в коде. Некоторые примеры: Правило редукции 1 АВ/С + АВ/С = АВ/С
А Б В
[я] 1 1 0
[к] 1 1 0
Разница 0 0 0. hi, hj, sb ложны (0), zb истинны (1). Код действия = 1. Таким образом, член [ j ] удаляется. Правило редукции 2 АВ + АВС/D = АВ
А Б В Г
[i] 0 1 х х
[к] 0 1 1 0
hi истинно, hj ложно, sb ложно, zb истинно. Код действия 1001 = 9 (десятичный). [j] удаляется. Правило редукции 3 А/ВС + АВС = А
А Б В Г Д Е
[i] 1 0 1 х х х
[к] 1 1 1 х х х
привет, hj, zb неверны. sb истинно (различно только B). Код действия 2. Переменная B в [i] удалена, все переменные [j] удалены. Правило редукции 4 АВ + А/ВС = АВ + АС
А Б В
[я] 1 1 х
[к] 1 0 1
привет, сб правда. zb, hj ложны. Разностный бит B удаляется в [ j ]. Правило сокращения 5, виртуальные термины AB + /BC —> AC, где AC — виртуальный термин, используемый только для сканирования.
А Б В
[я] 1 1 х
[j] х 0 1
привет, hj, sb верны. зб неверно.
Код действия 1110 = 14 десятичных знаков. Действие : Запускается сканирование для сравнения виртуального термина AC с каждым термином в таблице истинности. Правила 1..4 применяются с единственным ограничением, что [i] или [j] не могут быть удалены, потому что они являются родителями. Ниже приведена типичная информация обычного сканирования k — это индекс в таблице истинности (как i, j для нормального сканирования) Виртуальный термин может (по сравнению с терминами таблицы истинности) генерировать новые виртуальные термины. Эти термины хранятся в стеке (фактически в буфере FIFO) для последующей обработки. В таблице истинности родительские термины виртуального термина выделены красным. Виртуальные термины в работе Введение виртуальных терминов устраняет все прежние дополнительные правила за пределами 1..4Сначала позвольте мне объяснить, как возникла идея виртуальных терминов. Формула /BQ + /AP + AB привела к /B /P Q + AB + /AP + AQ Этот результат не является ошибочным, но указанный термин жир является избыточным (как и /P в / б/пк) Итак, AQ представляет собой /BQ + AB. Если AQ = 1, то наверняка /BQ + AB = 1 (но не наоборот). В этом случае термины /BQ + AB образуют виртуальный термин AQ. Пример 1: /AZ + /BZ + /CZ + ABC = Z + ABC Пример 2: BC + /BP + ACPQ = BC + /BP Пример 3: /B /P Q + AB + /AP + AQ . История Первую версию этого генератора/редуктора таблицы истинности я написал в 1991 году во время изучения математики.10 (наивысший балл) предлагалось каждому студенту, который мог написать программу для диагностики 902:30 формула логики высказывания как «непоследовательная» или «тавтология». Я написал программу на Turbo Pascal (под MSDOS) и набрал «10». В январе 2013 года, убираясь в своей комнате, я нашел старую дискету. Оказалось, что программа работала нормально, несмотря на старомодный пользовательский интерфейс, но некоторые таблицы где не сводится к пределу. Применялись только правила редукции 1..4. Я снова начал работать над этим. В результате появилась версия Logic10 1.  |