Меню

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



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

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

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

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

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

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

2. определить число строк в таблице по формуле m=2 n , где 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 3 = 8.

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

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

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

2. m строк=2 n , m=2 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. Построёте таблицу истинности для логического выражения

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

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

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

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

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

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

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

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

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

Очевидно, что значения заданной функции F совпадают со значениями выражения X\/ Y\/¬ Z. Следовательно, правильный ответ – 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 путями:

  • рассуждая над условием;
  • решая логические операции;
  • используя таблицы истинности.

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

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

  • Разобраться с условием на естественном языке, выделив простые высказывания, и дать им символьные обозначения (латиница).
  • Записать условие в виде формулы. Решить ее поэтапно, упрощая, учитывая приоритеты (( ), ¬, &, V).
  • Просчитать формулы строчно или при помощи таблиц истинности, учитывая законы алгебры логики.
  • Проверить, соответствует ли полученный результат условию задачи.

Табличный способ – этапы, особенности

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

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

Метод таблиц

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

Существует общий алгоритм построения таблиц:

  • Определить число логических значений/переменных (n) в примере.
  • Установить вид, число и тип операций. Важно заранее определить очередность действий, выразить это при помощи скобок.
  • Полученные данные позволяют рассчитать сколько нужно столбцов – это сумма числа переменных и операций.
  • Нарисовать таблицу, заполнить шапку, записав обозначение переменных и выбранные действия.
  • Определить, сколько существует наборов логических переменных (т.е. число строчек) по формуле m = 2 n + 1 (шапка).
  • Заполнить столбцы, вписав наборы значений логических переменных (0 или 1).
  • Записать результаты логических операций, указанных в шапке для каждой совокупности значений.
  • Сделать выводы на основании полученных результатов.

Если необходимо перебрать все значения простых выражений, то для задач:

  • с 2-мя переменными может быть только 4 набора логических переменных;

1 tablicy istinnosti

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

Обязательно учитывают приоритет операций:

  • Указанные в скобках.
  • Отрицание.
  • Логическая конъюнкция чисел.
  • Дизъюнкция.
  • Строгая дизъюнкция.
  • Импликация.
  • Эквивалентность.

Обозначение логических операций:

2 tablicy istinnosti

Сравнение методов решения

Метод рассуждений

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

Пример №1.

Андрей, Владимир, Георгий и Дмитрий живут на одной улице, они соседи. Они работают по таким специальностям: гитарист, плотник, егерь и стоматолог.

  • дом плотника правее егеря;
  • стоматолог проживает левее егеря;
  • дом гитариста с самого краю;
  • стоматолог живет рядом с гитаристом;
  • Владимир не гитарист, и его дом не соседствует с гитаристом;
  • дома Дмитрия и егеря соседние;
  • здание, в котором прописан Андрей, правее стоматолога;
  • между домами Андрея и Дмитрия один дом.

Чтобы рассуждать было проще, добавим изображение зданий, присвоим им номера:

3 tablicy istinnosti

Но стоматолог живет левее егеря, а правее егеря – плотник. Получается, что дом гитариста не может быть последним, а дом стоматолога не может быть предпоследними. То есть, егерь живет в предпоследнем доме:

4 tablicy istinnosti

Между домами Андрея и Дмитрия стоит один дом, значит, дом Андрея не может быть предпоследним, получается номер – 4, что автоматом исключает проживание там Дмитрия и Владимира.

Читайте также:  Шаг 3 Относительные и абсолютные ссылки изучаем Excel с нуля

5 tablicy istinnosti

Условие задачи заняло 2 предложения, а рассуждений получилось на 2 страницы.

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

Табличный метод

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

Чтобы построить таблицу истинности логических выражений, следует:

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

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

6 tablicy istinnosti

Рассмотрим тот же пример.

7 tablicy istinnosti

Определяем, что только гитарист может жить в первом доме, далее смотрим на заметки и условия и получаем таких жителей:

8 tablicy istinnosti

9 tablicy istinnosti

Метод компактнее, для некоторых задач нагляднее.

Построение таблиц истинности для различных типов задач

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

Пример 2.

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

Разобьём условие на 3 простые высказывания, присвоим им буквенные обозначения:

А — «Первый студент летал в Англию»;

В — «Второй студент летал в Англию»;

С — «Третий студент летал в Англию».

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

10 tablicy istinnosti

Пример 3.

Есть три 8-ых класса (А, В, С), которые соревнуются между собой за средний бал. Учителя в начале года сделали такие предположения:

  • Если А получит максимальный бал, то максимальный бал получат Ви С.
  • А и С получат или не получат максимальный бал одновременно.
  • Необходимым условием получения высшего бала С класса является получение высшего бала В классом.

По завершении года оказалось, что 2 предсказания оказались верными, а одно – ошибочным.

Выясним, какие же классы добились высшего бала.

Разбиваем условие задачи на элементарные высказывания:

А – «А добьется высшего бала»;

В – «В добьется высшего бала»;

С – «С добьется высшего бала».

Запишем логические операции, описанные в примере:

11 tablicy istinnosti

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

Пример 4.

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

  • последняя – гласная (Х1);
  • или первая буква согласная (Х2)
  • вторая – согласная (Х3).

Предложенные имена: Арина, Артур, Кэтрин, София.

Решим задачу, используя таблицу.

Сначала решим пошагово, выполняя операции по приоритету:

12 tablicy istinnosti

Указанному условию соответствует первое имя.

Пример 5.

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

Известно, что в олимпиаде по химии участвовали 4 ученицы 8 класса: Марина, Света, Саша и Галя. Они заняли первые 4 места. Какое место заняла каждая из девочек, если есть их высказывания о победителях, но в них лишь половина информации правдива – первая или вторая половина предложения.

Маша Марина: «Саша заняла второе место, а Света – первое».

Полина Света: «Нет, это не так, Саша – победительница, а Галя, – на втором месте».

Ольга Саша: «Зачем вы всех путаете? Третье место за Мариной, а Света – на четвертом месте».

Составляем таблица для перебора вариантов. Правду обозначаем «1», ложь – «0».

Берем любое (Марины) утверждение и принимаем его первую часть за правду. Значит, Саша – 2 место, тогда Света не 1-ое (вторая половина фразы – ложь), остальных девочек на 2 место ставим «0».

13 tablicy istinnosti

Берем утверждение второй девочки. Так как Саша не может быть победительницей, то в этой фразе первая часть – ложь, а вторая должна быть истинной. Но в нем и вторая часть – неверна (второе место за Сашей, мы так приняли в начале).Уже на второй фразе получается противоречие всему.

14 tablicy istinnosti

Итог: Победительницей олимпиады стала Светлана, на втором месте – Галина, на третьем – Марина, на последнем из четырех – Александра.

Построение электронных схем, реализующих логические операции

Если рассмотреть электросхемы с точки зрения логики, особенно компьютерные, то их также можно описать при помощи «1» и «0» – электричество идет или не идет по проводам.

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

Электросхема с конъюнктором

15 tablicy istinnosti

Рассмотрим все варианты:

  • Все контакты включены, тогда источник света горит.
  • Первый контакт в положении «выключено» – свет не горит.
  • Второй контакт выключен – лампа не светит.
  • Все контакты отключены – свет не горит.

Заключение – эта электрическая цепь реализует операцию «И».

Дизъюнктор, схема электропитания

16 tablicy istinnosti

Рассмотрим этот вид электрической цепочки:

  • Все контакты включены – лампа горит.
  • Первый контакт включен, второй выключен – свет горит.
  • Обратная ситуация – выключен первый, включен второй – лампа светится.
  • Все контакты выключены – света нет.

Заключение – такой вид электросхем соответствует логической операции «ИЛИ».

Инвертор в электросхемах

17 tablicy istinnosti

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

Заключение: схема соответствует логической операции «НЕ».

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

Обозначение логических элементов

18 tablicy istinnosti

Удобно создавать электросхемы в ПО SmartNotebook, которое используется с интерактивной доской.

Источник

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

План урока:

Способы решения задач по логике

Многие задачи можно решить, используя инструменты алгебры логики. Чтобы получить результат, можно пойти 3 путями:

  • рассуждая над условием;
  • решая логические операции;
  • используя таблицы истинности.

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

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

  • Разобраться с условием на естественном языке, выделив простые высказывания, и дать им символьные обозначения (латиница).
  • Записать условие в виде формулы. Решить ее поэтапно, упрощая, учитывая приоритеты (( ), ¬, &, V).
  • Просчитать формулы строчно или при помощи таблиц истинности, учитывая законы алгебры логики.
  • Проверить, соответствует ли полученный результат условию задачи.

Табличный способ – этапы, особенности

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

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

Читайте также:  Области при создании сводной таблицы

Метод таблиц

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

Существует общий алгоритм построения таблиц:

  • Определить число логических значений/переменных (n) в примере.
  • Установить вид, число и тип операций. Важно заранее определить очередность действий, выразить это при помощи скобок.
  • Полученные данные позволяют рассчитать сколько нужно столбцов – это сумма числа переменных и операций.
  • Нарисовать таблицу, заполнить шапку, записав обозначение переменных и выбранные действия.
  • Определить, сколько существует наборов логических переменных (т.е. число строчек) по формуле m = 2 n + 1 (шапка).
  • Заполнить столбцы, вписав наборы значений логических переменных (0 или 1).
  • Записать результаты логических операций, указанных в шапке для каждой совокупности значений.
  • Сделать выводы на основании полученных результатов.

Если необходимо перебрать все значения простых выражений, то для задач:

  • с 2-мя переменными может быть только 4 набора логических переменных;

1 tablicy istinnosti

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

Обязательно учитывают приоритет операций:

  • Указанные в скобках.
  • Отрицание.
  • Логическая конъюнкция чисел.
  • Дизъюнкция.
  • Строгая дизъюнкция.
  • Импликация.
  • Эквивалентность.

Обозначение логических операций:

2 tablicy istinnosti

Сравнение методов решения

Метод рассуждений

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

Пример №1.

Андрей, Владимир, Георгий и Дмитрий живут на одной улице, они соседи. Они работают по таким специальностям: гитарист, плотник, егерь и стоматолог.

  • дом плотника правее егеря;
  • стоматолог проживает левее егеря;
  • дом гитариста с самого краю;
  • стоматолог живет рядом с гитаристом;
  • Владимир не гитарист, и его дом не соседствует с гитаристом;
  • дома Дмитрия и егеря соседние;
  • здание, в котором прописан Андрей, правее стоматолога;
  • между домами Андрея и Дмитрия один дом.

Чтобы рассуждать было проще, добавим изображение зданий, присвоим им номера:

3 tablicy istinnosti

Но стоматолог живет левее егеря, а правее егеря – плотник. Получается, что дом гитариста не может быть последним, а дом стоматолога не может быть предпоследними. То есть, егерь живет в предпоследнем доме:

4 tablicy istinnosti

Между домами Андрея и Дмитрия стоит один дом, значит, дом Андрея не может быть предпоследним, получается номер – 4, что автоматом исключает проживание там Дмитрия и Владимира.

5 tablicy istinnosti

Условие задачи заняло 2 предложения, а рассуждений получилось на 2 страницы.

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

Табличный метод

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

Чтобы построить таблицу истинности логических выражений, следует:

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

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

6 tablicy istinnosti

Рассмотрим тот же пример.

7 tablicy istinnosti

Определяем, что только гитарист может жить в первом доме, далее смотрим на заметки и условия и получаем таких жителей:

8 tablicy istinnosti

9 tablicy istinnosti

Метод компактнее, для некоторых задач нагляднее.

Построение таблиц истинности для различных типов задач

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

Пример 2.

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

Разобьём условие на 3 простые высказывания, присвоим им буквенные обозначения:

А — «Первый студент летал в Англию»;

В — «Второй студент летал в Англию»;

С — «Третий студент летал в Англию».

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

10 tablicy istinnosti

Пример 3.

Есть три 8-ых класса (А, В, С), которые соревнуются между собой за средний бал. Учителя в начале года сделали такие предположения:

  • Если А получит максимальный бал, то максимальный бал получат Ви С.
  • А и С получат или не получат максимальный бал одновременно.
  • Необходимым условием получения высшего бала С класса является получение высшего бала В классом.

По завершении года оказалось, что 2 предсказания оказались верными, а одно – ошибочным.

Выясним, какие же классы добились высшего бала.

Разбиваем условие задачи на элементарные высказывания:

А – «А добьется высшего бала»;

В – «В добьется высшего бала»;

С – «С добьется высшего бала».

Запишем логические операции, описанные в примере:

11 tablicy istinnosti

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

Пример 4.

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

  • последняя – гласная (Х1);
  • или первая буква согласная (Х2)
  • вторая – согласная (Х3).

Предложенные имена: Арина, Артур, Кэтрин, София.

Решим задачу, используя таблицу.

Сначала решим пошагово, выполняя операции по приоритету:

12 tablicy istinnosti

Указанному условию соответствует первое имя.

Пример 5.

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

Известно, что в олимпиаде по химии участвовали 4 ученицы 8 класса: Марина, Света, Саша и Галя. Они заняли первые 4 места. Какое место заняла каждая из девочек, если есть их высказывания о победителях, но в них лишь половина информации правдива – первая или вторая половина предложения.

Маша Марина: «Саша заняла второе место, а Света – первое».

Полина Света: «Нет, это не так, Саша – победительница, а Галя, – на втором месте».

Ольга Саша: «Зачем вы всех путаете? Третье место за Мариной, а Света – на четвертом месте».

Составляем таблица для перебора вариантов. Правду обозначаем «1», ложь – «0».

Берем любое (Марины) утверждение и принимаем его первую часть за правду. Значит, Саша – 2 место, тогда Света не 1-ое (вторая половина фразы – ложь), остальных девочек на 2 место ставим «0».

13 tablicy istinnosti

Берем утверждение второй девочки. Так как Саша не может быть победительницей, то в этой фразе первая часть – ложь, а вторая должна быть истинной. Но в нем и вторая часть – неверна (второе место за Сашей, мы так приняли в начале).Уже на второй фразе получается противоречие всему.

14 tablicy istinnosti

Итог: Победительницей олимпиады стала Светлана, на втором месте – Галина, на третьем – Марина, на последнем из четырех – Александра.

Построение электронных схем, реализующих логические операции

Если рассмотреть электросхемы с точки зрения логики, особенно компьютерные, то их также можно описать при помощи «1» и «0» – электричество идет или не идет по проводам.

Читайте также:  Футбол чемпионат англии премьер лига таблица чемпионата

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

Электросхема с конъюнктором

15 tablicy istinnosti

Рассмотрим все варианты:

  • Все контакты включены, тогда источник света горит.
  • Первый контакт в положении «выключено» – свет не горит.
  • Второй контакт выключен – лампа не светит.
  • Все контакты отключены – свет не горит.

Заключение – эта электрическая цепь реализует операцию «И».

Дизъюнктор, схема электропитания

16 tablicy istinnosti

Рассмотрим этот вид электрической цепочки:

  • Все контакты включены – лампа горит.
  • Первый контакт включен, второй выключен – свет горит.
  • Обратная ситуация – выключен первый, включен второй – лампа светится.
  • Все контакты выключены – света нет.

Заключение – такой вид электросхем соответствует логической операции «ИЛИ».

Инвертор в электросхемах

17 tablicy istinnosti

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

Заключение: схема соответствует логической операции «НЕ».

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

Обозначение логических элементов

18 tablicy istinnosti

Удобно создавать электросхемы в ПО SmartNotebook, которое используется с интерактивной доской.

Источник

Информатика. 10 класс

Конспект урока

Информатика, 10 класс. Урок № 11.

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

Перечень вопросов, рассматриваемых в теме: высказывание, логическая переменная, логические операции (отрицание, конъюнкция, дизъюнкция, строгая дизъюнкция, импликация, эквиваленция), логические выражения, предикаты и их множества истинности, таблицы истинности и их анализ.

Глоссарий по теме: импликация, эквиваленция, предикат, примеры законов алгебры логики.

Основная литература по теме урока:

Л. Л. Босова, А. Ю. Босова. Информатика. Базовый уровень: учебник для 10 класса

— М.: БИНОМ. Лаборатория знаний, 2017 (с.174—197)

Открытые электронные ресурсы по теме:

Теоретический материал для самостоятельного изучения:

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

Алгебра логики возникла в середине XIX века в трудах английского математика Джорджа Буля. Ее создание представляло собой попытку решать традиционные логические задачи алгебраическими методами. В 1938 году Клод Шеннон применил алгебру логики для описания процесса функционирования релейно-контактных и электронно-ламповых схем. Логическое высказывание — это повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.

Например, предложение «Джордж Буль — основоположник алгебры логики» истинно, а «Солнце — спутник Земли» ложно.

Употребляемые в обычной речи логические связки «не», «и», «или», «если…то», «тогда и только тогда» и др. позволяют из уже заданных высказываний строить новые высказывания. Высказывания, образованные из других высказываний, называются составными. Высказывание, никакая часть которого не является высказыванием, называется элементарным. Например, из двух простых высказываний (каких?) можно получить следующее составное высказывание: «Алгебра логики является основой строения логических схем компьютеров и служит математической основой решения сложных логических задач». Истинность или ложность составных высказываний зависит от истинности или ложности образующих их высказываний и определённой трактовки связок (логических операций над высказываниями).

Обоснование истинности или ложности элементарных высказываний не является задачей алгебры логики. Эти вопросы решаются теми науками, к сфере которых относятся элементарные высказывания. Такое сужение интересов позволяет обозначать высказывания символическими именами (например, А, В, С).

Логическая переменная — это переменная, которая обозначает любое высказывание и может принимать логические значения «истина» или «ложь». Для логических значений «истина» — «ложь» могут использоваться следующие обозначения: И — Л, true — false, да — нет, 1 — 0.

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

В алгебре логики имеется шесть логических операций. Из курса информатики 8—9 классов вам знакомы три из них:

— отрицание (инверсия, логическое НЕ)

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

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

Высказывание истинно тогда и только тогда, когда истинны оба исходных высказывания.

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

Высказывание ложно тогда и только тогда, когда ложны оба исходных высказывания.

Рассмотрим новые логические операции.

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

Операция импликации обозначается символом и задается следующей таблицей истинности:

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

Импликацию можно заменить на выражение, использующее ранее изученные операции НЕ и ИЛИ:

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

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

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

Строгую дизъюнкцию можно представить через базовые операции следующим образом:

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

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

В логике эквиваленция обозначается символом и задается следующей таблицей истинности:

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

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

Можно заменить эквивалентность выражением, которое включает только базовые логические операции:

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

Для логического выражения справедливо:

  1. всякая логическая переменная, а также логические константы (0,1) есть логическое выражение;
  2. если — логическое выражение, то и — логическое выражение;
  3. если A и B — выражения, то связанные любой бинарной операцией, они также представляют собой логическое выражение.

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

  1. отрицание;
  2. конъюнкция;
  3. дизъюнкция, строгая дизъюнкция;
  4. импликация, эквиваленция.

Операции одного приоритета выполняются в порядке их следования, слева направо. Как в математике, скобки меняют порядок выполнения операций.

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

Источник