Разделы сайта
Выбор редакции:
- Скачать программу сервисы google play на андроид
- Видеоплееры для windows - выбираем лучший видео проигрыватель для компьютера
- Бесплатные программы для записи CD-DVD дисков на русском языке: Список лучших
- Узнаем как отформатировать флешку если она защищена от записи
- Использование телефона в качестве модема
- Установка Ubuntu LINUX с флешки - инструкция
- Лучшие компактные смартфоны по отзывам покупателей
- Как узнать какие платные подписки и услуги подключены на ваш номер МТС и отключить их?
- Бюджетная колонка S28 Portable Mini Wireless Bluetooth V3
- Распиновка микро USB разъема
Реклама
3 составить таблицу истинности логического выражения. Прочие логические функции |
Основано на: демонстрационных вариантах ЕГЭ по информатике за 2015 год, на учебнике Босовой Людмилы Леонидовны В предыдущей части 1 мы разобрали с вами логические операции Дизъюнкция и Конъюнкция , нам с вами осталось разобрать инверсию и перейти к решению задания ЕГЭ. Инверсия
Для записи инверсии используются следующие знаки: НЕ, `¯` , `¬ ` Инверсия определяется следующей таблицей истинности:
Любое сложное высказывание можно записать в виде логического выражения — выражения, содержащего логические переменные, знаки логических операций и скобки. Логические операции в логи-ческом выражении выполняются в следующей очерёдности: инвер-сия, конъюнкция, дизъюнкция. Изменить порядок выполнения опе-раций можно с помощью расстановки скобок. Логические операции имеют следующий приоритет: инверсия, конъюнк-ция, дизъюнкция. И так, перед нами задание №2 из ЕГЭ по информатике 2015 года
Значительно облегчает решение задания то, что в каждом варианте сложного выражения F только одна логическая операция: умножение или сложение. В случае умножения /\ если хотя бы одна переменная будет равна нулю, то значение всего выражения F так же должно быть равно нулю. А в случае со сложением V если хотя бы одна переменная будет равна единице, то значение всего выражения F должно быть равно 1. Тех данных, которые есть в таблице по каждой из 8 переменных выражения F, нам вполне достаточно для решения. Проверим выражение номер 1:
Проверим выражение номер 2:
Проверим выражение номер 3:
Проверим выражение номер 4:
В решении задания на едином государственном экзамене вам нужно поступать точно таким же образом: отбрасывать те варианты, которые точно не подходят по тем данным, которые есть в таблице. Оставшийся возможный вариант (как в нашем случае вариант номер 2) и будет правильным ответом. Проблема определения истинности выражения встаёт перед многими науками. Любая доказательная дисциплина должна опираться на некоторые критерии истинности доказательств. Наука, изучающая эти критерии, называется алгеброй логики. Основной постулат алгебры логики заключается в том, что любое самое витиеватое утверждение может быть представлено в виде алгебраического выражения из более простых утверждений, истинность или ложность которых легко определить. Для любого "алгебраического" действия над утверждением задаётся правило определения истинности или ложности измененного утверждения, исходя из истинности или ложности исходного утверждения. Эти правила записываются через таблицы истинности выражения . Прежде, чем составлять таблицы истинности, надо поближе познакомиться с алгеброй логики. Алгебраические преобразования логических выраженийЛюбое логическое выражение, как и его переменные (утверждения), принимают два значения: ложь или истина . Ложь обозначается нулём, а истина - единицей. Разобравшись с областью определения и областью допустимых значений, мы можем рассмотреть действия алгебры логики. ОтрицаниеОтрицание и инверсия - самое простое логическое преобразование. Ему соответствует частица "не." Это преобразование просто меняет утверждение на противоположное. Соответственно, значение утверждения тоже меняется на противоположное. Если утверждение А истинно, то "не А" - ложно. Например, утверждение "прямой угол - это угол, равный девяносто градусов" - истина. Тогда его отрицание "прямой угол не равен девяноста градусам" - ложь. Таблица истинности для отрицания будет такова: ДизъюнкцияЭта операция может быть обычной или строгой , их результаты будут различаться. Обычная дизъюнкция или логическое сложение соответствует союзу "или". Она будет истинной если хотя бы одно из утверждений, входящих в неё - истина. Например, выражение "Земля круглая или стоит на трёх китах" будет истинным, так как первое утверждение - истинно, хоть второе и ложно.В таблице это будет выглядеть так: Строгую дизъюнкцию или сложение по модулю также называют "исключающим или" . Эта операция может принимать вид грамматической конструкции "одно из двух: либо..., либо...". Здесь значение логического выражения будет ложным, если все утверждения, входящие в него, имеют одинаковую истинность. То есть, оба утверждения либо вместе истинны, либо вместе ложны. Таблица значений исключающего или Импликация и эквивалентностьИмпликация представляет собой следствие и грамматически может быть выражена как "из А следует Б". Здесь утверждение А будет называться предпосылкой, а Б - следствием. Импликация может быть ложной, только в одном случае: если предпосылка истинна, а следствие ложно. То есть, ложь не может следовать из истины. Во всех остальных случаях импликация истинна. Варианты, когда оба утверждения имеют одинаковую истинность, вопросов не вызывают. Но почему верное следствие из неверной предпосылки - истина? Дело в том, что из ложной предпосылки может следовать что угодно. Это и отличает импликацию от эквивалентности. В математике (и других доказательных дисциплинах) импликация используется для указания необходимого условия. Например, утверждение А - "точка О - экстремум непрерывной функции", утверждение Б - "производная непрерывной функции в точке О обращается в ноль". Если О, действительно, точка экстремума непрерывной функции, то производная в этой точке будет, и вправду, равна нулю. Если же О не является точкой экстремума, то производная в этой точке может быть нулевой, а может не быть. То есть Б необходимо для А, но не достаточно. Таблица истинности для импликации выглядит следующим образом: Логическая операция эквивалентность, по сути, является взаимной импликацией . "А эквивалентно Б" означает, что "из А следует Б" и "из Б следует А" одновременно. Эквивалентность верна, когда оба утверждения либо одновременно верные, либо одновременно неверные. В математике эквивалентность используется для определения необходимого и достаточного условия. Например, утверждение А - "Точка О является точкой экстремума непрерывной функции", утверждение Б - "В точке О производная функции обращается в ноль и меняет знак". Эти два утверждения эквивалентны. Б содержит необходимое и достаточное условие для А. Обратите внимание, что в данном примере утверждений Б на самом деле является конъюнкцией двух других: "производная в точке О обращается в ноль" и "производная в точке О меняет знак". Прочие логические функцииВыше были рассмотрены основные логические операции, которые часто используются. Есть и другие функции, которые используются:
Построение таблиц истинностиЧтобы построить таблицу истинности для какого-либо логического выражения, надо действовать в соответствии с алгоритмом:
В итоге последний столбец отобразит значение всего выражения в зависимости от значения переменных. Отдельно следует сказать о порядке логических действий . Как его определить? Здесь, как и в алгебре, есть правила, задающие последовательность действий. Они выполняются в следующем порядке:
ПримерыДля закрепления материала можно попробовать составить таблицу истинности для ранее упомянутых логических выражений. Рассмотрим три примера:
Штрих ШеффераШтрих Шеффера - это логическое выражение, которое можно записать в виде "не (А и Б)". Здесь две переменные, и два действия. Конъюнкция в скобках, значит, она выполняется первой. В таблице будет шапка и четыре строки со значениями переменных, а также четыре столбца. Заполним таблицу:
Отрицание конъюнкции выглядит как дизъюнкция отрицаний. Это можно проверить, если составить таблицу истинности для выражения "не А или не Б". Проделайте это самостоятельно и обратите внимание, что здесь будет уже три операции. Стрелка ПирсаРассматривая Стрелку Пирса, которая представляет собой отрицание дизъюнкции "не (А или Б)", сравним её с конъюнкцией отрицаний "не А и не Б". Заполним две таблицы:
Значения выражений совпали. Изучив два эти примера, можно прийти к выводу, как раскрывать скобки после отрицания: отрицание применяется ко всем переменным в скобках, конъюнкция меняется на дизъюнкцию, а дизъюнкция - на конъюнкцию. Определение эквивалентностиПро утверждения А и Б можно сказать, что они эквивалентны, тогда и только тогда, когда из А следует Б и из Б следует А. Запишем это как логическое выражение и построим для него таблицу истинности. "(А эквивалентно Б) эквивалентно (из А следует Б) и (из Б следует А)". Здесь две переменных и пять действий. Строим таблицу: В последнем столбце все значения истинные. Это значит, что приведенное определение эквивалентности верно при любых значениях А и Б. Значит, оно всегда истинно. Именно так с помощью таблицы истинности можно проверить корректность любых определений и логических построений. Продолжительность урока: 45 мин Тип урока: комбинированный:
Цели урока:
План урока:
Оборудование и программный материал:
Ход урока I. Организационный момент Мы продолжаем изучение темы “Основы логики”. На предыдущих уроках мы увидели, что логика достаточно крепко связана с нашей повседневной жизнью, а также увидели, что почти любое высказывание можно записать в виде формулы. II. Повторение материала предыдущего урока Давайте вспомним основные определения и понятия:
III. Объяснение нового материала Последние два примера относятся к сложным высказываниям. Как же определить истинность сложных высказываний? Мы говорили, что она вычисляется. Для этого в логике существуют таблицы для вычисления истинности составных (сложных) высказываний. Они называются таблицами истинности. Итак, тема урока ТАБЛИЦЫ ИСТИННОСТИ. 3.1) Определение. Таблица истинности – это таблица, показывающая истинность сложного высказывания при всех возможных значениях входящих переменных (Рисунок 1). 3.2) Разберем подробнее каждую логическую операцию в соответствии с ее определением: 1. Инверсия (отрицание) – это логическая операция, которая каждому простому высказыванию ставит в соответствие составное высказывание, заключающееся в том, что исходное высказывание отрицается. Эта операция относится только к одной переменной, поэтому для нее отведено только две строки, т.к. одна переменная может иметь одно из двух значений: 0 или 1. 2. Конъюнкция (умножение)– это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания истинны. Легко увидеть, что данная таблица действительно похожа на таблицу умножения. 3. Дизъюнкция (сложение) – это логическая операция, которая каждым двум простым высказываниям ставит в соответствие составное высказывание, являющееся ложным тогда и только тогда, когда оба исходных высказывания ложны. Можно убедиться, что таблица похожа на таблицу сложения кроме последнего действия. В двоичной системе счисления 1 + 1 = 10, в десятичной – 1 + 1 = 2. В логике значения переменной 2 невозможно, рассмотрим 10 с точки зрения логики: 1 – истинно, 0 – ложно, т.о. 10 – истинно и ложно одновременно, чего быть не может, поэтому последнее действие строго опирается на определение. 4. Импликация (следование) – это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся ложным тогда и только тогда, когда условие истинное, а следствие ложно. 5. Эквиваленция (равносильность) – это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания одновременно истинны или ложны. Последние две операции были разобраны нами на предыдущем уроке. 3.3) Разберем алгоритм составления таблицы истинности для сложного высказывания: 3.4) Рассмотрим пример составления таблицы истинности для сложного высказывания: Пример. Построить таблицу истинности для формулы: А U В -> ¬А U С. Решение (Рисунок 2) Из примера видно, что таблицей истинности является не все решение, а только последнее действие (столбец, выделенный красным цветом). IV. Закрепление. Для закрепления материала вам предлагается решить самостоятельно примеры под буквами а, б, в, дополнительно г–ж (Рисунок 3). V. Домашнее задание, обобщение материала. Домашнее задание дано вам также на экране монитора (Рисунок 4) Обобщение материала: сегодня на уроке мы научились определять истинность составных высказываний, но больше с математической точки зрения, так как вам были даны не сами высказывания, а формулы, отображающие их. На следующих уроках мы закрепим эти умения и постараемся их применить к решению логических задач. Определение 1 Логическая функция – функция, переменные которой принимают одно из двух значений: $1$ или $0$. Любую логическую функцию можно задать с помощью таблицы истинности: набор всех возможных аргументов записывается в левой части таблицы, а соответствующие значения логической функции – в правой части. Определение 2 Таблица истинности – таблица, которая показывает, какие значения примет составное выражение при всех возможных наборах значений простых выражений, входящих в него. Определение 3 Равносильными называются логические выражения, последние столбцы таблиц истинности которых совпадают. Равносильность обозначается с помощью знака $«=»$. При составлении таблицы истинности важно учитывать следующий порядок выполнения логических операций: Рисунок 1. Приоритетом в выполнении порядка выполнения операций пользуются скобки. Алгоритм построения таблицы истинности логической функцииОпределяют количество строк: кол-во строк = $2^n + 1$ (для строки заголовка) , $n$ – количество простых выражений. Например, для функций двух переменных существует $2^2 = 4$ комбинации наборов значений переменных, для функций трех переменных – $2^3 = 8$ и т.д. Определяют количество столбцов: кол-во столбцов = кол-во переменных + кол-во логических операций. При определении количества логических операций учитывают также порядок их выполнения. Заполняют столбцы результатами выполнения логических операций в определенной последовательности, учитывая таблицы истинности основных логических операций. Рисунок 2. Пример 1 Составить таблицу истинности логического выражения $D=\bar{A} \vee (B \vee C)$. Решение:
Определим количество строк: кол-во строк = $2^3 + 1=9$. Количество переменных – $3$. Заполним таблицу, учитывая таблицы истинности логических операций. Рисунок 3. Пример 2 По данному логическому выражению построить таблицу истинности: Решение:
Определим количество строк: Количество простых выражений – $n=3$, значит кол-во строк = $2^3 + 1=9$. Определим количество столбцов: Количество переменных – $3$. Количество логических операций и их последовательность: Таблица истинности – таблица содержащая все возможные комбинации входных переменных и соответствующее им значения на выходе. Таблица истинности содержит 2 n строк, где n – число входных переменных, и n+m – столбцы, где m – выходные переменные. Инструкция
. При вводе с клавиатуры используйте следующие обозначения:
Например, логическое выражение abc+ab~c+a~bc необходимо ввести так: a*b*c+a*b=c+a=b*c
Правила ввода логической функции
Проектирование и анализ логических схем ЭВМ ведётся с помощью специального раздела математики - алгебры логики. В алгебре логики можно выделить три основные логические функции: "НЕ" (отрицание), "И" (конъюнкция), "ИЛИ" (дизъюнкция).
Рисунок1- Схема логического устройства Все операции алгебры логики определяются таблицами истинности значений. Таблица истинности определяет результат выполнения операции для всех возможны х логических значений исходных высказываний. Количество вариантов, отражающих результат применения операций, будет зависеть от количества высказываний в логическом выражении. Если число высказываний в логическом выражении N, то таблица истинности будет содержать 2 N строк, так как существует 2 N различных комбинаций возможных значений аргументов. Операция НЕ - логическое отрицание (инверсия)Логическая операция НЕ применяется к одному аргументу, в качестве которого может быть и простое, и сложное логическое выражение. Результатом операции НЕ является следующее:
не А, Ā, not A, ¬А, !A Результат операции отрицания НЕ определяется следующей таблицей истинности:
Результат операции отрицания истинен, когда исходное высказывание ложно, и наоборот. Операция ИЛИ - логическое сложение (дизъюнкция, объединение)Логическая операция ИЛИ выполняет функцию объединения двух высказываний, в качестве которых может быть и простое, и сложное логическое выражение. Высказывания, являющиеся исходными для логической операции, называют аргументами. Результатом операции ИЛИ является выражение, которое будет истинным тогда и только тогда, когда истинно будет хотя бы одно из исходных выражений.Применяемые обозначения: А или В, А V В, A or B, A||B. Результат операции ИЛИ определяется следующей таблицей истинности: Результат операции ИЛИ истинен, когда истинно А, либо истинно В, либо истинно и А и В одновременно, и ложен тогда, когда аргументы А и В - ложны. Операция И - логическое умножение (конъюнкция)Логическая операция И выполняет функцию пересечения двух высказываний (аргументов), в качестве которых может быть и простое, и сложное логическое выражение. Результатом операции И является выражение, которое будет истинным тогда и только тогда, когда истинны оба исходных выражения.Применяемые обозначения: А и В, А Λ В, A & B, A and B. Результат операции И определяется следующей таблицей истинности:
Результат операции И истинен тогда и только тогда, когда истинны одновременно высказывания А и В, и ложен во всех остальных случаях. Операция «ЕСЛИ-ТО» - логическое следование (импликация)Эта операция связывает два простых логических выражения, из которых первое является условием, а второе - следствием из этого условия.Применяемые обозначения: если А, то В; А влечет В; if A then В; А→ В. Таблица истинности:
Результат операции следования (импликации) ложен только тогда, когда предпосылка А истинна, а заключение В (следствие) ложно. Операция «А тогда и только тогда, когда В» (эквивалентность, равнозначность)Применяемое обозначение: А ↔ В, А ~ В.Таблица истинности:
Операция «Сложение по модулю 2» (XOR, исключающее или, строгая дизъюнкция)Применяемое обозначение: А XOR В, А ⊕ В.Таблица истинности:
Результат операции эквивалентность истинен только тогда, когда А и В одновременно истинны или одновременно ложны. Приоритет логических операций
Совершенная дизъюнктивная нормальная формаСовершенная дизъюнктивная нормальная форма формулы (СДНФ) это равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций, обладающая свойствами:
Для каждой функции СДНФ и СКНФ определены единственным образом с точностью до перестановки. Совершенная конъюнктивная нормальная формаСовершенная конъюнктивная нормальная форма формулы (СКНФ) это равносильная ей формула, представляющая собой конъюнкцию элементарных дизъюнкций, удовлетворяющая свойствам:
|
Читайте: |
---|
Популярное:
Новое
- Видеоплееры для windows - выбираем лучший видео проигрыватель для компьютера
- Бесплатные программы для записи CD-DVD дисков на русском языке: Список лучших
- Узнаем как отформатировать флешку если она защищена от записи
- Использование телефона в качестве модема
- Установка Ubuntu LINUX с флешки - инструкция
- Лучшие компактные смартфоны по отзывам покупателей
- Как узнать какие платные подписки и услуги подключены на ваш номер МТС и отключить их?
- Бюджетная колонка S28 Portable Mini Wireless Bluetooth V3
- Распиновка микро USB разъема
- Кастрация защищенных аккумуляторов Sanyo и Panasonic и небольшой ликбез по Li-ion