Элементы алгебры логики таблица истинности

Элементы алгебры логики таблица истинности

Ключевые слова:

  • алгебра логики
  • высказывание
  • логическая операция
  • конъюнкция
  • дизъюнкция
  • отрицание
  • логическое выражение
  • таблица истинности
  • законы логики

1.3.1. Высказывание

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

Для информатики важен раздел математики, называемый алгеброй логики; объектами алгебры логики являются высказывания.

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

Например, относительно предложений «Великий русский учёный М. В. Ломоносов родился в 1711 году» и «Two plus six Is eight» можно однозначно сказать, что они истинны. Предложение «Зимой воробьи впадают в спячку» ложно. Следовательно, эти предложения являются высказываниями.

В русском языке высказывания выражаются повествовательными предложениями. Но не всякое повествовательное предложение является высказыванием.

Например, предложение «Это предложение является ложным» не является высказыванием, так как относительно него нельзя сказать, истинно оно или ложно, без того, чтобы не получить противоречие. Действительно, если принять, что предложение истинно, то это противоречит сказанному. Если же принять, что предложение ложно, то отсюда следует, что оно истинно.

Относительно предложения «Компьютерная графика — самая интересная тема в курсе школьной информатики» также нельзя однозначно сказать, истинно оно или ложно. Подумайте сами почему.

Побудительные и вопросительные предложения высказываниями не являются.

Например, не являются высказываниями такие предложения, как: «Запишите домашнее задание», «Как пройти в библиотеку?», «Кто к нам пришёл?».

Высказывания могут строиться с использованием знаков различных формальных языков — математики, физики, химии и т. п.

Примерами высказываний могут служить:

  1. «Na — металл» (истинное высказывание);
  2. «Второй закон Ньютона выражается формулой F=m•а» (истинное высказывание);
  3. «Периметр прямоугольника с длинами сторон a и b равен а • b» (ложное высказывание).

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

  1. «3 + 5 = 2 • 4» (истинное высказывание);
  2. «II + VI > VIII» (ложное высказывание).

Не являются высказываниями и равенства или неравенства, содержащие переменные. Например, предложение «X n — 1;

  • провести заполнение таблицы по столбцам, выполняя логические операции в соответствии с установленной последовательностью.
  • Построим таблицу истинности для логического выражения A ∨ А & В. В нём две переменные, две операции, причём сначала выполняется конъюнкция, а затем — дизъюнкция. Всего в таблице будет четыре столбца:

    Наборы входных переменных — это целые числа от О до 3, представленные в двухразрядном двоичном коде: 00, 01, 10, 11. Заполненная таблица истинности имеет вид:

    Обратите внимание, что последний столбец (результат) совпал со столбцом А. В таком случае говорят, что логическое выражение A ∨ А & Б равносильно логическому выражению А.

    1.3.4. Свойства логических операций

    Рассмотрим основные свойства (законы) алгебры логики.

      Переместительный (коммутативный) закон

        для логического умножения:

    для логического сложения:

    Сочетательный (ассоциативный) закон

      для логического умножения:

    для логического сложения:

    (A ∨ B) ∨ C = A ∨(B ∨ C).

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

    Распределительный (дистрибутивный) закон

      для логического умножения:

    для логического сложения:

    A ∨ (B & С) = (A ∨ В) & (A ∨ С).

    Двойное отрицание исключает отрицание.

    Закон исключения третьего

      для логического умножения:


    для логического сложения:

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

      для логического умножения:

    для логического сложения:

    Законы операций с 0 и 1

      для логического умножения:
    Читайте также:  74Hc595d описание на русском

    для логического сложения:

    A ∨ O = A; A ∨ l = l.

    Законы общей инверсии

      для логического умножения:


    для логического сложения:

    Законы алгебры логики могут быть доказаны с помощью таблиц истинности.

    Докажем распределительный закон для логическического сложения:

    A ∨ (В & С) = (А ∨ В) & (A ∨ С).

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

    Пример 2. Найдём значение логического выражения для числа Х = 0.

    Решение. При X = 0 получаем следующее логическое выражение: . Так как логические выражения 0 1 .

    1 С учётом того, что ваза разбита одним внуком, можно было составлять не всю таблицу, а только её фрагмент, содержащий следуюнще наборы входных переменных: 001, 010, 100.

    Исходя из того, что знает о внуках бабушка, следует искать в таблице строки, содержащие в каком-либо порядке три комбинации значений: 00, 11, 01 (или 10). Таких строк в таблице оказалось две (они отмечены галочками). Согласно второй из них, вазу разбили Коля и Вася, что противоречит условию. Согласно первой из найденных строк, вазу разбил Серёжа, он же оказался хитрецом. Шутником оказался Вася. Имя правдивого внука — Коля.

    Задача 2. В соревнованиях по гимнастике участвуют Алла, Валя, Сима и Даша. Болельщики высказали предположения о возможных победителях:

    1. Сима будет первой, Валя — второй;
    2. Сима будет второй, Даша — третьей;
    3. Алла будет второй, Даша — четвёртой.

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

    Решение. Рассмотрим простые высказывания:

    C1 = «Сима заняла первое место»;

    В2 = «Валя заняла второе место»;

    С2 = «Сима заняла второе место»;

    Д3 = «Даша заняла третье место»;

    А2 = «Алла заняла второе место»;

    Д4 = «Даша заняла четвёртое место».

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

    1. C1 + В2 = 1, С1 • В2 = 0;
    2. С2 + Д3 = 1, С2 • Д3 = 0;
    3. А2 + Д4 = 1, А2 • Д4 = 0.

    Логическое произведение истинных высказываний будет истинным:

    На основании распределительного закона преобразуем левую часть этого выражения:

    Высказывание С1 • С2 означает, что Сима заняла и первое, и второе места. Согласно условию задачи, это высказывание ложно. Ложным является и высказывание В2 • С2. Учитывая закон операций с константой 0, запишем:

    Дальнейшее преобразование левой части этого равенства и исключение заведомо ложных высказываний дают:

    Из последнего равенства следует, что С1 = 1, Д3 = 1, А2 = 1. Это означает, что Сима заняла первое место, Алла — второе, Даша — третье. Следовательно, Валя заняла четвёртое место.

    Познакомиться с другими способами решения логических задач, а также принять участие в Интернет-олимпиадах и конкурсах по их решению вы сможете на сайте «Математика для школьников» (http://www.kenqyry.com/).

    На сайте http://www.kaser.com/ вы сможете скачать демонстрационную версию очень полезной, развивающей логику и умение рассуждать логической головоломки Шерлок.

    1.3.6. Логические элементы

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

    Вы уже знаете, что любая информация может быть представлена в дискретной форме — в виде фиксированного набора отдельных значений. Устройства, которые обрабатывают такие значения (сигналы), называются дискретными. Дискретный преобразователь, который выдаёт после обработки двоичных сигналов значение одной из логических операций, называется логическим элементом.

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

    Рис 1.5.
    Логические элементы

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

    Читайте также:  Телевизор супра не включается индикатор горит зеленым

    Логический элемент ИЛИ (дизъюнктор) реализует операцию логического сложения (рис. 1.5, б). Если хотя бы на одном входе будет единица, то на выходе элемента также будет единица.

    Логический элемент НЕ (инвертор) реализует операцию отрицания (рис. 1.5, в). Если на входе элемента О, то на выходе 1 и наоборот.

    Компьютерные устройства, производящие операции над двоичными числами, и ячейки, хранящие данные, представляют собой электронные схемы, состоящие из отдельных логических элементов. Более подробно эти вопросы будут раскрыты в курсе информатики 10-11 классов.

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

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

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

    Составить более полное представление о логических элементах и электронных схемах вам поможет работа с тренажёром «Логика» (http://kpolyakov. narod. ru/prog/logic. htm).

    Самое главное

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

    Основные логические операции, определённые над высказываниями: инверсия, конъюнкция, дизъюнкция.

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

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

    Вопросы и задания


    Рассмотрите представленные на рисунке электрические схемы:

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


    Некоторый сегмент сети Интернет состоит из 1000 сайтов. Поисковый сервер в автоматическом режиме составил таблицу ключевых слов для сайтов этого сегмента. Вот её фрагмент:

    По запросу сомики & гуппи было найдено 0 сайтов, по запросу сомики & меченосцы — 20 сайтов, а по запросу меченосцы & гуппи — 10 сайтов.

    Сколько сайтов будет найдено по запросу сомики | меченосцы | гуппи?

    Для скольких сайтов рассматриваемого сегмента ложно высказывание «Сомики — ключевое слово сайта ИЛИ меченосцы — ключевое слово сайта ИЛИ гуппи — ключевое слово сайта»?
    Постройте таблицы истинности для следующих логических выражений:

  • Проведите доказательство рассмотренных в параграфе логических законов с помощью таблиц истинности.
  • Даны три числа в десятичной системе счисления: А = 23, B = 19, С = 26. Переведите А, B и С в двоичную систему счисления и выполните поразрядно логические операции (A ∨ B) & С. Ответ дайте в десятичной системе счисления.
  • Найдите значения выражений:

  • Найдите значение логического выражения для указанных значений числа X:

    Пусть А = «Первая буква имени — гласная», В = «Четвёртая буква имени согласная». Найдите значение логического выражения для следующих имён:

    4) ФЁДОР

    Разбирается дело Джона, Брауна и Смита. Известно, что один из них нашёл и утаил клад. На следствии каждый из подозреваемых сделал два заявления:

    Смит: «Я не делал этого. Браун сделал это».

    Джон: «Браун не виновен. Смит сделал это».

    Браун: «Я не делал этого. Джон не делал этого».

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

    Читайте также:  Как найти ушедшего кота
  • Алёша, Боря и Гриша нашли в земле старинный сосуд. Рассматривая удивительную находку, каждый высказал по два предположения:
  • Алеша: «Это сосуд греческий и изготовлен в V веке».
  • Боря: «Это сосуд финикийский и изготовлен в III веке».
  • Гриша: «Это сосуд не греческий и изготовлен в IV веке».
    Учитель истории сказал ребятам, что каждый из них прав только в одном из двух предположений. Где и в каком веке изготовлен сосуд?
  • Выясните, какой сигнал должен быть на выходе электронной схемы при каждом возможном наборе сигналов на входах. Составьте таблицу работы схемы. Каким логическим выражением описывается схема?
  • Электронное приложение к уроку

    Презентации, плакаты, текстовые файлы Вернуться к материалам урока Ресурсы ЭОР

    Cкачать материалы урока

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

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

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

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

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

    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 столбцов.

    Инструкция . При вводе с клавиатуры используйте следующие обозначения:

    Клавиша Оператор
    ! ¬ Отрицание (НЕ)
    | | Штрих Шеффера (И-НЕ)
    # Стрелка Пирса (ИЛИ-НЕ)
    * & Конъюнкция (И)
    + v Дизъюнкция (ИЛИ)
    ^ Исключающее ИЛИ, сумма по модулю 2 (XOR)
    @ Импликация (ЕСЛИ-ТО)
    % Обратная импликация
    = ≡ (

    , ↔)

    Эквивалентность (РАВНО)

    bc необходимо ввести так: a*b*c+a*b=c+a=b*c
    Для ввода данных в виде логической схемы используйте этот сервис.

    Правила ввода логической функции

    1. Вместо символа v (дизъюнкция, ИЛИ) используйте знак + .
    2. Перед логической функцией не надо указывать обозначение функции. Например, вместо F(x,y)=(x|y)=(x^y) необходимо ввести просто (x|y)=(x^y) .
    3. Максимальное количество переменных равно 10 .

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

    Ссылка на основную публикацию
    Adblock detector