По таблице истинности составить логическую функцию. Глоссарий, определения логики
И , которых Вам будет достаточно для решения сложных логических выражений. Также мы рассмотрим порядок выполнения данных логических операций в сложных логических выражениях и представим таблицы истинности для каждой логической операции. Советуем Вам воспользоваться нашими программами для решения задач по математике, и . Помоми большого количества программ для решения задач на сайте работает , на котором Вы всегда можете задать вопрос и на котором Вам всегда помогуть с решением задач. Пользуйтесь нашими сервисами на здоровье!
Глоссарий, определения логики
Высказывание - это повествовательное предложение, про которое можно определенно сказать истинно оно или ложно (истина (логическая 1), ложь (логический 0)).
Логические операции - мыслительные действия, результатом которых является изменение содержания или объема понятий, а также образование новых понятий.
Логическое выражение - устное утверждение или запись, в которое, наряду с постоянными величинами, обязательно входят переменные величины (объекты). В зависимости от значений этих переменных величин (объектов) логическое выражение может принимать одно из двух возможных значений: истина (логическая 1) или ложь (логический 0).
Сложное логическое выражение - логическое выражение, состоящее из одного или нескольких простых логических выражений (или сложных логических выражений), соединенных с помощью логических операций.
Логические операции и таблицы истинности
1) Логическое умножение или конъюнкция:
Конъюнкция - это сложное логическое выражение, которое считается истинным в том и только том случае, когда
оба простых выражения являются истинными, во всех остальных случаях данное сложеное выражение ложно.
Обозначение: F = A & B.
Таблица истинности для конъюнкции
3) Логическое отрицание или инверсия:
Инверсия - это сложное логическое выражение, если исходное логическое выражение истинно, то результат отрицания будет ложным, и наоборот, если исходное логическое выражение ложно, то результат отрицания будет истинным. Другими простыми слова, данная операция означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО.
Таблица истинности для инверсии
5) Логическая равнозначность или эквивалентность:
Эквивалентность - это сложное логическое выражение, которое является истинным тогда и только тогда, когда оба простых логических выражения имеют одинаковую истинность.
Таблица истинности для эквивалентности
| A | B | F |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 1 |
Порядок выполнения логических операций в сложном логическом выражении
1. Инверсия;
2. Конъюнкция;
3. Дизъюнкция;
4. Импликация;
5. Эквивалентность.
Для изменения указанного порядка выполнения логических операций используются скобки.
Проблема определения истинности выражения встаёт перед многими науками. Любая доказательная дисциплина должна опираться на некоторые критерии истинности доказательств. Наука, изучающая эти критерии, называется алгеброй логики. Основной постулат алгебры логики заключается в том, что любое самое витиеватое утверждение может быть представлено в виде алгебраического выражения из более простых утверждений, истинность или ложность которых легко определить.
Для любого "алгебраического" действия над утверждением задаётся правило определения истинности или ложности измененного утверждения, исходя из истинности или ложности исходного утверждения. Эти правила записываются через таблицы истинности выражения . Прежде, чем составлять таблицы истинности, надо поближе познакомиться с алгеброй логики.
Алгебраические преобразования логических выражений
Любое логическое выражение, как и его переменные (утверждения), принимают два значения: ложь или истина . Ложь обозначается нулём, а истина - единицей. Разобравшись с областью определения и областью допустимых значений, мы можем рассмотреть действия алгебры логики.
Отрицание
Отрицание и инверсия - самое простое логическое преобразование. Ему соответствует частица "не." Это преобразование просто меняет утверждение на противоположное. Соответственно, значение утверждения тоже меняется на противоположное. Если утверждение А истинно, то "не А" - ложно. Например, утверждение "прямой угол - это угол, равный девяносто градусов" - истина. Тогда его отрицание "прямой угол не равен девяноста градусам" - ложь.
Таблица истинности для отрицания будет такова:
Дизъюнкция
Эта операция может быть обычной или строгой , их результаты будут различаться.
Обычная дизъюнкция или логическое сложение соответствует союзу "или". Она будет истинной если хотя бы одно из утверждений, входящих в неё - истина. Например, выражение "Земля круглая или стоит на трёх китах" будет истинным, так как первое утверждение - истинно, хоть второе и ложно.В таблице это будет выглядеть так:
Строгую дизъюнкцию или сложение по модулю также называют "исключающим или" . Эта операция может принимать вид грамматической конструкции "одно из двух: либо..., либо...". Здесь значение логического выражения будет ложным, если все утверждения, входящие в него, имеют одинаковую истинность. То есть, оба утверждения либо вместе истинны, либо вместе ложны.
Таблица значений исключающего или
Импликация и эквивалентность
Импликация представляет собой следствие и грамматически может быть выражена как "из А следует Б". Здесь утверждение А будет называться предпосылкой, а Б - следствием. Импликация может быть ложной, только в одном случае: если предпосылка истинна, а следствие ложно. То есть, ложь не может следовать из истины. Во всех остальных случаях импликация истинна. Варианты, когда оба утверждения имеют одинаковую истинность, вопросов не вызывают. Но почему верное следствие из неверной предпосылки - истина? Дело в том, что из ложной предпосылки может следовать что угодно. Это и отличает импликацию от эквивалентности.
В математике (и других доказательных дисциплинах) импликация используется для указания необходимого условия. Например, утверждение А - "точка О - экстремум непрерывной функции", утверждение Б - "производная непрерывной функции в точке О обращается в ноль". Если О, действительно, точка экстремума непрерывной функции, то производная в этой точке будет, и вправду, равна нулю. Если же О не является точкой экстремума, то производная в этой точке может быть нулевой, а может не быть. То есть Б необходимо для А, но не достаточно.
Таблица истинности для импликации выглядит следующим образом:
Логическая операция эквивалентность, по сути, является взаимной импликацией . "А эквивалентно Б" означает, что "из А следует Б" и "из Б следует А" одновременно. Эквивалентность верна, когда оба утверждения либо одновременно верные, либо одновременно неверные.
В математике эквивалентность используется для определения необходимого и достаточного условия. Например, утверждение А - "Точка О является точкой экстремума непрерывной функции", утверждение Б - "В точке О производная функции обращается в ноль и меняет знак". Эти два утверждения эквивалентны. Б содержит необходимое и достаточное условие для А. Обратите внимание, что в данном примере утверждений Б на самом деле является конъюнкцией двух других: "производная в точке О обращается в ноль" и "производная в точке О меняет знак".
Прочие логические функции
Выше были рассмотрены основные логические операции, которые часто используются. Есть и другие функции, которые используются:
- Штрих Шеффера или несовместимость представляет собой отрицание конъюнкции А и Б
- Стрелка Пирса представляет сбой отрицание дизъюнкции.
Построение таблиц истинности
Чтобы построить таблицу истинности для какого-либо логического выражения, надо действовать в соответствии с алгоритмом:
- Разбить выражение на простые утверждения и обозначить каждое из них как переменную.
- Определить логические преобразования.
- Выявить порядок действий этих преобразований.
- Сосчитать строки в будущей таблице. Их количество равно два в степени N, где N - число переменных, плюс одна строка для шапки таблицы.
- Определить число столбцов. Оно равно сумме количества переменных и количества действий. Можно представлять результат каждого действия в виде новой переменной, если так будет понятней.
- Шапка заполняется последовательно, сначала все переменные, потом результаты действий в порядке их выполнения.
- Заполнение таблицы надо начать с первой переменной. Для неё количество строк делится пополам. Одна половина заполняется нулями, вторая - единицами.
- Для каждой следующей переменной нули и единицы чередуются вдвое чаще.
- Таким образом заполняются все столбцы с переменными и для последней переменной значение меняется в каждой строке.
- Потом последовательно заполняются результаты всех действий.
В итоге последний столбец отобразит значение всего выражения в зависимости от значения переменных.
Отдельно следует сказать о порядке логических действий . Как его определить? Здесь, как и в алгебре, есть правила, задающие последовательность действий. Они выполняются в следующем порядке:
- выражения в скобках;
- отрицание или инверсия;
- конъюнкция;
- строгая и обычная дизъюнкция;
- импликация;
- эквивалентность.
Примеры
Для закрепления материала можно попробовать составить таблицу истинности для ранее упомянутых логических выражений. Рассмотрим три примера:
- Штрих Шеффера.
- Стрелка Пирса.
- Определение эквивалентности.
Штрих Шеффера
Штрих Шеффера - это логическое выражение, которое можно записать в виде "не (А и Б)". Здесь две переменные, и два действия. Конъюнкция в скобках, значит, она выполняется первой. В таблице будет шапка и четыре строки со значениями переменных, а также четыре столбца. Заполним таблицу:
| А | Б | А и Б | не (А и Б) |
| Л | Л | Л | И |
| Л | И | Л | И |
| И | Л | Л | И |
| И | И | И | Л |
Отрицание конъюнкции выглядит как дизъюнкция отрицаний. Это можно проверить, если составить таблицу истинности для выражения "не А или не Б". Проделайте это самостоятельно и обратите внимание, что здесь будет уже три операции.
Стрелка Пирса
Рассматривая Стрелку Пирса, которая представляет собой отрицание дизъюнкции "не (А или Б)", сравним её с конъюнкцией отрицаний "не А и не Б". Заполним две таблицы:
| А | Б | не А | не Б | не А и не Б |
| Л | Л | И | И | И |
| Л | И | И | Л | Л |
| И | Л | Л | И | И |
| И | И | Л | Л | Л |
Значения выражений совпали. Изучив два эти примера, можно прийти к выводу, как раскрывать скобки после отрицания: отрицание применяется ко всем переменным в скобках, конъюнкция меняется на дизъюнкцию, а дизъюнкция - на конъюнкцию.
Определение эквивалентности
Про утверждения А и Б можно сказать, что они эквивалентны, тогда и только тогда, когда из А следует Б и из Б следует А. Запишем это как логическое выражение и построим для него таблицу истинности. "(А эквивалентно Б) эквивалентно (из А следует Б) и (из Б следует А)".
Здесь две переменных и пять действий. Строим таблицу:
В последнем столбце все значения истинные. Это значит, что приведенное определение эквивалентности верно при любых значениях А и Б. Значит, оно всегда истинно. Именно так с помощью таблицы истинности можно проверить корректность любых определений и логических построений.
Определение 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)$.
Решение:
- инверсия ($\bar{A}$);
- дизъюнкция, т.к. она находится в скобках ($B \vee C$);
дизъюнкция ($\overline{A}\vee \left(B\vee C\right)$) – искомое логическое выражение.
Кол-во столбцов = $3 + 3=6$.
Определим количество строк:
кол-во строк = $2^3 + 1=9$.
Количество переменных – $3$.
Заполним таблицу, учитывая таблицы истинности логических операций.
Рисунок 3.
Пример 2
По данному логическому выражению построить таблицу истинности:
Решение:
- отрицание ($\bar{C}$);
- дизъюнкция, т.к. она находится в скобках ($A \vee B$);
- конъюнкция ($(A\vee B)\bigwedge \overline{C}$);
- отрицание, которое обозначим $F_1$ ($\overline{(A\vee B)\bigwedge \overline{C}}$);
- дизъюнкция ($A \vee C$);
- конъюнкция ($(A\vee C)\bigwedge B$);
- отрицание, которое обозначим $F_2$ ($\overline{(A\vee C)\bigwedge B}$);
дизъюнкция – искомая логическая функция ($\overline{(A\vee B)\bigwedge \overline{C}}\vee \overline{(A\vee C)\bigwedge B}$).
Определим количество строк:
Количество простых выражений – $n=3$, значит
кол-во строк = $2^3 + 1=9$.
Определим количество столбцов:
Количество переменных – $3$.
Количество логических операций и их последовательность:
Страница 1
Урок информатики по теме "Основы логики, таблицы истинности"
Тема: Как построить таблицу истинности?
Продолжительность урока: 40 минТип урока: комбинированный:
проверка знаний – устная работа;
новый материал – лекция;
закрепление – практические упражнения;
проверка знаний – задания для самостоятельной работы.
Обучающие:
Научить составлять логические выражения из высказываний
Ввести понятие “таблица истинности”
Изучить последовательность действий построения таблиц истинности
Научить находить значение логических выражений посредством построения таблиц истинности
Развивающие:
Развивать логическое мышление
Развивать внимание
Развивать память
Развивать речь учащихся
Воспитательные:
Воспитывать умение слушать учителя и одноклассников
Воспитывать аккуратность ведения тетради
Воспитывать дисциплинированность
Организационный момент (2 мин).
Повторение материала предыдущего урока +проверка домашнего задания (устный опрос) (5 мин).
Объяснение нового материала (10 мин).
Физкультминутка (1 мин).
Закрепление
разбор примера (5 мин);
практические упражнения (10 мин);
задания для самостоятельной работы (5 мин).
белая доска;
раздаточный справочный материал “Таблицы истинности”;
демонстрация презентации “Таблицы истинности”.
1. Организационный момент
Приветствие.
Проверка отсутствующих в классе.
Объявление оценок за прошлый урок.
3 учащихся работают по карточкам:
Соедините правильные определения или обозначения:
|
1. Логика |
1. |
|
2. Высказывание |
2. Логическое сложение |
|
3. Алгебра логики |
3. Наука о формах и способах мышления |
|
4. Логическая переменная |
4. Логическое отрицание |
|
5. Дизъюнкция |
5. ИСТИНА и ЛОЖЬ |
|
6. Инверсия |
6.  |
|
7. Конъюнкция |
7.  |
|
8. Импликация |
8. Наука об операциях над высказываниями |
|
9. Эквивалентность |
9. Повествовательное предложения, в котором что-либо утверждается или отрицается, которое может быть истинным или ложным |
Остальные устно.
1)Примеры записаны на доске:
Для логических выражений сформулируйте составные высказывания на обычном языке:
Б) (X=Y) и (X=Z). (Ответ: числа X , Y и Z равны между собой)
2) Приведите примеры составных высказываний из школьных предметов и запишите их с помощью логических операций: литература, биология, география, история.
Какие логические связки вы использовали? (Инверсия, дизъюнкция и конъюнкция)
Мы увидели, что логика достаточно крепко связана с нашей повседневной жизнью, а также увидели, что почти любое высказывание можно записать в виде формулы.
Давайте вспомним основные определения и понятия:
3. Объяснение нового материала
Из составного высказывания составьте формулу, заменяя простые высказывания переменными.
Задача: В классе оказалось разбито стекло. Учитель объясняет директору: это сделал Коля или Саша. Но Саша этого не делал, так как в это время сдавал мне зачет. Следовательно, это сделал Коля.
Решение: Формализуем данное сложное высказывание:
К – это сделал Коля; С – это сделал Саша.
Форма высказывания:
На прошлом уроке мы находили значение составного высказывания путем подстановки исходных значений входящих логических переменных. А сегодня мы узнаем, что можно построить таблицу истинности, которая определяет истинность или ложность логического выражения при всех возможных комбинациях исходных значений простых высказываний (логических переменных) и, что можно определить значения исходных логических переменных, зная какой нам нужен результат.
Итак, тема сегодняшнего урока: «Как построить таблицу истинности?»
Мы уже несколько уроков подряд используем понятие “таблица истинности”? так что же такое таблица истинности ?
Таблица истинности – это таблица, истинность сложного высказывания при всевозможных значениях входящих переменных.
Еще раз рассмотрим наш пример
и построим таблицу истинности для этого составного высказывания
При построении таблиц истинности есть определенная последовательность действий. Давайте запишем
Необходимо определить количество строк в таблице истинности.
количество строк = 2 n , где n – количество логических переменных
Необходимо определить количество столбцов в таблице истинности.
количество столбцов = количеству логических переменных + количество логических операций.
Необходимо построить таблицу истинности с указанным количеством строк и столбцов, ввести названия столбцов таблицы в соответствии с последовательностью выполнения логических операций с учетом скобок и приоритетов (¬, &, V);
Заполнить столбцы входных переменных наборами значений
Провести заполнение таблицы истинности по столбцам, выполняя логические операции в соответствии с установленной последовательностью.
|
К |
С |
 |
 |
 |
|
|
0 |
0 |
1 |
0 |
0 |
1 |
|
0 |
1 |
0 |
1 |
0 |
1 |
|
1 |
0 |
1 |
1 |
1 |
1 |
|
1 |
1 |
0 |
1 |
0 |
1 |
4. Физкультминутка
Закрепление
разбор примера.
практические упражнения.
задания для самостоятельной работы.
А) 
|
А |
В |
 |
 |
|
0 |
0 |
0 |
1 |
|
0 |
1 |
0 |
0 |
|
1 |
0 |
0 |
0 |
|
1 |
1 |
1 |
0 |
Б) 
|
А |
В |
 |
 |
|
|
0 |
0 |
1 |
0 |
1 |
|
0 |
1 |
0 |
1 |
0 |
|
1 |
0 |
1 |
1 |
1 |
|
1 |
1 |
0 |
1 |
0 |
В) 
|
А |
В |
С |
|
 |
|
|
0 |
0 |
0 |
1 |
0 |
0 |
|
0 |
0 |
1 |
1 |
1 |
1 |
|
0 |
1 |
0 |
0 |
0 |
0 |
|
0 |
1 |
1 |
0 |
0 |
0 |
|
1 |
0 |
0 |
1 |
0 |
1 |
|
1 |
0 |
1 |
1 |
1 |
1 |
|
1 |
1 |
0 |
0 |
0 |
1 |
|
1 |
1 |
1 |
0 |
0 |
1 |
Задание для самостоятельной работы «Кто быстрей?»
Заготовленные карточки учащимся, в которой надо провести заполнение таблицы истинности по столбцам, выполняя логические операции в соответствии с установленной последовательностью.
|
А |
В |
С |
|
|||
Ответ:
|
А |
В |
С |
|
|
 |
 |
|
0 |
0 |
0 |
1 |
0 |
1 |
0 |
|
0 |
0 |
1 |
0 |
0 |
0 |
1 |
|
0 |
1 |
0 |
1 |
0 |
1 |
0 |
|
0 |
1 |
1 |
0 |
0 |
0 |
1 |
|
1 |
0 |
0 |
1 |
0 |
1 |
0 |
|
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
1 |
1 |
0 |
1 |
1 |
1 |
0 |
|
1 |
1 |
1 |
0 |
1 |
1 |
0 |
Обобщение урока, домашнее задание (2 мин).
Д/З не задается, так как урок спаренный, дети приходят через урок и продолжаем изучать тему «Основы логики и логические основы компьютера».
страница 1
При составлении таблицы истинности для логического выражения необходимо:
Выяснить количество строк в таблице (вычисляется как 2 n , где n – количество переменных).
Выяснить количество столбцов (определяется как количество переменных + количество логических операций).
Установить последовательность выполнения логических операций.
Построить таблицу, указывая названия столбцов и возможные наборы значений исходных логических переменных.
Заполнить таблицу истинности по столбцам.
Контрольный пример . Построить таблицу истинности для выражения F = (A V B) & (¬A V ¬B).
Количество строк в таблице определяется как 2 2 (2 переменных) + 1 (заголовок таблицы) = 5.
Количество столбцов – как 2 логические переменные (A, B) + 5 логических операций (&, V, ¬, →, ↔).
Расставим порядок выполнения операций:
(A V B) & (¬A V ¬B).
Построим таблицу истинности для данного логического выражения (таблица 5).
Таблица 5 – Таблица истинности для логического выражения
|
(A V B) & (¬A V ¬B) |
||||||
Контрольный пример . Построить таблицу истинности для логического выражения X V Y & ¬Z.
Количество строк = 2 3 + 1 = 9.
Количество столбцов = 3 логические переменные + 3 логических операций = 6.
Укажем порядок действий:
Нарисуем и заполним таблицу 6:
Таблица 6 – Таблица истинности для логического выражения
1.4 Построение логических схем
С точки зрения логики электрический ток либо течет, либо не течет; электрический импульс есть или нет; электрическое напряжение есть или нет. Рассмотрим электрические контактные схемы, реализующие логические операции (схемы 1 – 3). На схемах 1 – 3 контакты обозначены латинскими буквами A и B.
Схема 1 – Конъюнкция Схема 2 – Дизъюнкция Схема 3 – Инверсия
(автоматический ключ)
Схема 4 – Конъюнктор Схема 5 – Дизъюнктор Схема 6 – Инвертор
Цепь на схеме 1 с последовательным соединением контактов соответствует логической операции «И» и представляется конъюнктором (схема 4). Цепь на схеме 2 с параллельным соединением контактов соответствует логической операции «ИЛИ» и представляется дизъюнктором (схема 5). Цепь на схеме 3 (электромагнитное реле) соответствует логической операции «НЕ» и представляется инвертором (схема 6).
Именно такие электронные схемы нашли свое применение в качестве элементной базы ЭВМ. Элементы, реализующие базовые логические операции, назвали базовыми логическими элементами или вентилями и характеризуются они не состоянием контактов, а наличием сигналов на входе и выходе элемента. Их названия и условные обозначения являются стандартными и используются при составлении и описании логических схем компьютера.
Логические схемы необходимо строить из минимально возможного количества элементов, что, в свою очередь, обеспечивает большую скорость работы и увеличивает надежность устройства.
Правило построения логических схем:
Определить число логических переменных.
Определить количество базовых логических операций и их порядок.
Изобразить для каждой логической операции соответствующий ей вентиль.
Соединить вентили в порядке выполнения логических операций.
Контрольный пример. Пусть X = Истина (1), Y = Ложь (0). Составьте логическую схему для следующего логического выражения: F = X V Y & X.
1) Две переменные –X и Y.
2) Две логические операции: X V Y & X.
3) Строим схему (рисунок 3).
4) Ответ: 1 V 0 & 1 = 1.
Рисунок 3 – Логическая схема для логического выражения F = X V Y & X