Меню

Задачи с решениями построение таблиц истинности информатика



Таблица истинности логических операций — алгоритм построения

Определения и понятия

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

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

Обычно значениями истинности описывают логическую функцию, у которой показатели параметров определяют верность. Раздел математики рассматривающий их на правдивость или ложность называется булевым. В 1854 году английский учёный Джордж Буль предложил метод, позволяющий проводить анализ классов и высказываний. Согласно ему, любое значение может принимать одно из двух состояний — истина или ложь.

Эти состояния принято обозначать арабскими цифрами один либо ноль или словами true и false. Это возможно из-за того, что для математики важна только истинность высказываний, а конкретное содержание второстепенно. Простые высказывания принято считать логическими переменными, а сложные — функциями логики. Выражения для упрощения записи обозначают латинскими буквами A, B, C.

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

Суждение о правильности построения таблиц истинности для логических выражений основано на учёте всех переменных и операций, последовательно выполняющихся в рассматриваемой функции. Обычно для начертания используют 2 n +1 строк, где n обозначает количество входных переменных, и n+m столбцов, m — число значений на выходе.

Виды логических операций

В качестве наименьшей единицы измерения объёма данных принято считать бит. В него заносится одно из двух значений — ложь (0) или правда (1). Каждая ячейка, соответствующая биту, находится лишь в одном из этих состояний. Существуют определённые операции, используемые для действий с ячейками:

  1. AND (И) — применяется для сравнения двух бит. Результатом действия будет единица, но лишь в том случае, если значения двух ячеек одинаковое. При остальных вариантах итог будет иметь устойчивое нулевое состояние.
  2. OR (ИЛИ) — по сути, операция обратная AND. Результат становится нулевым, если содержимое двух сравниваемых бит одинаковое. В остальных случаях он равный единице.
  3. XOR (ИЛИ) — если значения, содержащиеся в двух сравниваемых битах противоположны, при выполнении логического действия результат будет равный единице. Во всех остальных случаях он будет равняться нулю.
  4. NOT (НЕ) — действие, используемое для одного бита. Если первоначально ячейка находилась в нулевом состоянии, то после выполнения над ней операции она станет равной единице и наоборот. Фактические это логическая инверсия.

Эти операции являются основными элементами при составлении таблиц истинности и получения возможного результата. На основании их построена алгебра Буля. Некоторые элементы получаются путём объединения нескольких операций. Так, существует состояние: NAND (И-НЕ) и NOR (ИЛИ-НЕ). Первый элемент является инверсией операции «И», а второй — «ИЛИ». На основании рассмотренных операторов строится работа всех цифровых интегральных схем.

В информатике существует своя терминология, обозначающая то или иное логическое действие. Так, AND называют операцией конъюнкции, OR — дизъюнкции, XOR — сложение по модулю 2, NOT — отрицание. Задача инженера при анализе схем или алгоритма сводится к выполнению булевой арифметики и упрощению выражений. Для этого используют различные правила и положения не требующих доказательства.

Аксиомы и законы

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

  1. Торжества. Записывается в виде утверждения: А = А. В этом случае таблица будет состоять из двух комбинаций: ложной и правдивой. Бинарная логическая связка «Если А, то А» является материальной импликацией. Для такого варианта всегда можно сказать, что А есть А. Этот закон обозначает то, что нельзя подменять одно понятие другим, иначе возникнут логические ошибки.
  2. Противоречия. Согласно ему, утверждение, что А и НЕ-А, неверно: A & A = 0. Другими словами, если А истинное значение, то его отрицание не может быть ложным. То есть их перемножение будет всегда фальшивой операцией. Этот закон довольно часто применяется для упрощения сложных логических суждений.
  3. Третьего исключённого. Закон записывается в виде A v A = 1 и обозначает, что в один и тот же момент высказывание может быть только правдивым или ложным. То есть третьего не дано.

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

Для решения логических задач с помощью таблиц истинности используют различные формулы, соответствующие разного вида операциям. Одно из них логическое умножение (конъюнкция). В этом случае считается, что функция истинная лишь тогда, когда оба выражения являются верными: F = A & B. Другое логическое сложение (дизъюнкция). Оно гласит, что если оба выражения ложны, то и логическая функция будет неверной.

Кроме того, используется закон:

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

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

Алгоритм построения

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

  • подсчитывают количество переменных n;
  • вычисляют число строк для будущей таблицы используя формулу m = 2n+1;
  • определяют число логических операций;
  • устанавливают порядок выполнения операций в соответствии со скобками и приоритетами;
  • строят таблицу с указанием столбцов и наборов значений, заданных логических операций;
  • заполняют оставшиеся ячейки в таблице.

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

Пример задания

Пусть необходимо построить таблицу для логического выражения F = (A → B) * (A + B). Эта формула состоит из двух логических переменных A и B и нескольких операций. Начинают построение с определения строк. Используя формулу 2n+1 для рассматриваемого примера можно установить, что их число будет: x = 22 + 1 = 5.

Читайте также:  Игра для изучения таблицы умножения

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

  1. Импликация в первой скобке.
  2. Инверсия во второй скобке переменной A.
  3. Отрицание во второй скобке неизвестной B.
  4. Сложение во втором члене.
  5. Конъюнкция.

В итоге получится, что столбцов будет: Y = 2 + 5 = 7. Теперь нужно построить таблицу 7Х5. В шапку первого и второго столбца вписывают переменные, а затем операции над ними. Затем в строках, соответствующих A и B нужно записать всё, что с ними может произойти. В итоге останется только правильно посчитать последний столбец.

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

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

Например, заданно выражение (x + y + z) * (x + y). По сути, оно записано в совершенно нормальной конъюнктивной форме. Но для приведения его к этому виду нужно, чтобы во втором выражении стояла z. Для того чтобы её добавить необходимо обратить внимание на то, что внутри скобок стоит логическое сложение. Поэтому дописав к нему ноль, результат не изменится. Добавить ноль через z можно, как ноль умножить на НЕ z. В итоге получится выражение (x + y + z) * (x + y + z + z), для которого, используя алгоритм составить таблицу уже не так и сложно.

Вычисления онлайн

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

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

Из различных порталов можно отметить три наиболее популярных калькулятора:

  1. Allcalc.
  2. Programforyou.
  3. Uchim.

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

Источник

Задачи с решениями построение таблиц истинности информатика

Логическая функция F задаётся выражением ((yz) ∨ (¬xw)) ≡ (wz).

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

Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z, w.

В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Пример. Пусть задано выражение xy, зависящее от двух переменных x и y, и фрагмент таблицы истинности:

Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.

Подберём переменные так, чтобы, выражение было истинно и при этом все переменные кроме одной были равны 0. Такой набор переменных: x = 1, y = 0, z = 0, w = 0. Сопоставляя полученные значения со второй строкой таблицы, получаем, что четвёртая переменная — это переменная x.

Рассмотрим первую строку таблицы. Последовательно рассмотрим случаи, когда y = 1, z = 1, w = 1. В первых двух случаях выражение ложно, а в третьем — истинно, следовательно, вторая переменная — переменная w.

Читайте также:  Общественное сознание обществознание 11 класс базовый уровень презентация к уроку по обществознанию 11 класс на тему

Рассмотрим третью строку таблицы. Заметим, что w = 1, значит, для того, чтобы выражение было истинно z должно быть равно 0. Вторая и четвёртая переменные — w и x, первая переменная равна 0, следовательно, z — первая переменная.

Таким образом, оставшаяся переменная, переменная 3 — это переменная y.

Приведем другое решение.

Составим таблицу истинности функции F и выпишем наборы переменных, при которых функция принимает значение 1. В наборах будем указывать переменные в порядке x, y, z, w. Получим следующие наборы:

(0, 0, 0, 0), (0, 0, 1, 1), (0, 1, 1, 1), (1, 0, 0, 0), (1, 0, 1, 1), (1, 1, 0, 1), (1, 1, 1, 1).

Рассмотрим вторую строку заданной таблицы. Она может соответствовать только набору переменных: x = 1, y = 0, z = 0, w = 0. Тогда четвертый столбец таблицы — это переменная x.

Рассмотрим первую строку заданной таблицы. Заметим, что в первой колонке должна стоять 1, так как наборов переменных, где были бы три нуля, больше нет. Тогда вторая строка может соответствовать только набору x = 0, y = 0, z = 1, w = 1. Следовательно, первая и вторая колонки соответствуют переменным z или w, а третья колонка — это переменная y.

Рассмотрим третью строку таблицы. В ней одна из переменных z или w равна 1, а другая 0. Следовательно, третьей строке может соответствовать только набор переменных x = 1, y = 1, z = 0, w = 1. Тогда первый столбец таблицы — это переменная z, а второй столбец — это переменная w.

Источник

Задачи с решениями построение таблиц истинности информатика

Логическая функция F задаётся выражением ((yz) ∨ (¬xw)) ≡ (wz).

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

Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z, w.

В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Пример. Пусть задано выражение xy, зависящее от двух переменных x и y, и фрагмент таблицы истинности:

Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.

Подберём переменные так, чтобы, выражение было истинно и при этом все переменные кроме одной были равны 0. Такой набор переменных: x = 1, y = 0, z = 0, w = 0. Сопоставляя полученные значения со второй строкой таблицы, получаем, что четвёртая переменная — это переменная x.

Рассмотрим первую строку таблицы. Последовательно рассмотрим случаи, когда y = 1, z = 1, w = 1. В первых двух случаях выражение ложно, а в третьем — истинно, следовательно, вторая переменная — переменная w.

Рассмотрим третью строку таблицы. Заметим, что w = 1, значит, для того, чтобы выражение было истинно z должно быть равно 0. Вторая и четвёртая переменные — w и x, первая переменная равна 0, следовательно, z — первая переменная.

Таким образом, оставшаяся переменная, переменная 3 — это переменная y.

Приведем другое решение.

Составим таблицу истинности функции F и выпишем наборы переменных, при которых функция принимает значение 1. В наборах будем указывать переменные в порядке x, y, z, w. Получим следующие наборы:

(0, 0, 0, 0), (0, 0, 1, 1), (0, 1, 1, 1), (1, 0, 0, 0), (1, 0, 1, 1), (1, 1, 0, 1), (1, 1, 1, 1).

Рассмотрим вторую строку заданной таблицы. Она может соответствовать только набору переменных: x = 1, y = 0, z = 0, w = 0. Тогда четвертый столбец таблицы — это переменная x.

Рассмотрим первую строку заданной таблицы. Заметим, что в первой колонке должна стоять 1, так как наборов переменных, где были бы три нуля, больше нет. Тогда вторая строка может соответствовать только набору x = 0, y = 0, z = 1, w = 1. Следовательно, первая и вторая колонки соответствуют переменным z или w, а третья колонка — это переменная y.

Рассмотрим третью строку таблицы. В ней одна из переменных z или w равна 1, а другая 0. Следовательно, третьей строке может соответствовать только набор переменных x = 1, y = 1, z = 0, w = 1. Тогда первый столбец таблицы — это переменная z, а второй столбец — это переменная w.

Источник

Решение логических задач таблицами истинности

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

1. Организационный момент.

Здравствуйте, ребята. Тема урока: Решение логических задач таблицами истинности. Сегодня у нас необычный урок, а урок “расследование, прокурорская проверка”. Я сегодня буду в роли “главного прокурора”, а вы мои “сыщики”. Сегодня мы узнаем ответы на многие интересующие нас вопросы из жизни нашей школы. Но прежде чем начать наше прокурорскую проверку, прошу всех получить погоны, на которые вы будете прикреплять звёздочки и получать звания “отличник”, “хорошист”, “плохиш”. Последнее звучит не очень красиво, поэтому будем стараться его не получать.

Базироваться мы с вами будем на Логических задачах.

Вопрос: Что такое логические задачи, для чего они нам нужны?

Ответ: Логические задачи развивают умение анализировать данные,

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

Вопрос: В каких профессиях применяются логические навыки?

Читайте также:  Роль средств массовой информации в жизни общества 11 й класс

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

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

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

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

Нам сегодня тоже придётся логически поразмышлять, чтобы раскрыть некоторые дела школы. Прежде чем начать “прокурорскую проверку” приказываю пройти всем тренировку.

3. Актуализация полученных знаний.

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

4. Изучение нового материала.

Существует не одна методика раскрытия преступлений…. Одну из них “Метод решения логических задач таблицами истинности” мы с вами рассмотрим. Для этого необходимо:

  1. Внимательно изучить условие задачи;
  2. Выделить простые высказывания и обозначить их буквами;
  3. Записать условие задачи на языке алгебры логики;
  4. Составить единое логическое выражение для всех требований задачи;
  5. Построить таблицу истинности для рассматриваемого выражения;
  6. Найти набор значений переменных, при которых выражение является истинным;
  7. Проанализировать полученный результат.

Ребята, каждый день в школе происходит какое-либо происшествие. Давайте поможем директору школы раскрыть некоторые из них. Учитель показывает папки ДЕЛ.

Итак вот наши дела:

Дело о хищении телефона Аликовой.
Дело о хулиганстве. Разбитое стекло.
Дело о вымогательстве.
Дело о разборках в классе.
и т.д.

Дело о хищении телефона Аликовой.

Фигуранты дела: Иванов, Петров и Сидоров.

Допрос: на вопрос “Кто из троих обучающихся взял телефон Аликовой?” был получен следующий ответ: “Неверно, что если телефон Аликовой брал Петров, то и Сидоров брал телефон Аликовой, и если телефон взял Иванов, то Петров не брал”. Кто взял телефон Аликовой?

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

И=телефон взял Иванов;
П=телефон взял Петров;
С=телефон взял Сидоров.

Вопрос: Какие логические обороты использовались в ответе?

Ответ: “Если…, то….”, “И…” и “Неверно, что…”

Запишем ответ на языке алгебры логики:

Построим таблицу истинности:

И П С П→С ¬ (П→С) ¬ П И→¬ П ¬ (П→С)T (И→¬П)
1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1 1
1 1 1
1 1 1 1

Проанализировав таблицу истинности видно, что выражение истинно в единственном случае, когда И=0, П=1 и С=0.

Следовательно телефон Аликовой взял Петров.

5. Закрепление полученных знаний на практике.

Разделить класс на три отдела расследований, каждый из которых будет расследовать только одно высказывание.

Дело о хулиганстве. Разбитое стекло.

Три ученика, Симонов Саша, Кузин Коля и Вишнёв Ваня, играли во дворе школы в футбол и разбили мячом окно. На вопрос кто разбил окно были получены следующие ответы.

Ваня сказал: “Это я разбил окно, Коля окно не разбивал”.

Коля сказал: “Это сделал не я и не Саша”.

Саша сказал: “Это сделал не я и не Ваня”.

Но дежурная сидела и всё видела. Она сказала, что только один ученик говорит правду, но не назвала его фамилии. Кто из учеников разбил стекло?

Фигуранты дела: Симонов Саша, Кузин Коля и Вишнёв Ваня.

Допрос: на вопрос “Кто разбил окно?” были получены следующие ответы:

Ваня сказал: “Это я разбил окно, Коля окно не разбивал”.

Коля сказал: “Это сделал не я и не Саша”.

Саша сказал: “Это сделал не я и не Ваня”.

Но дежурная сидела и всё видела. Она сказала, что только один ученик говорит правду, но не назвала его фамилии.

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

В=разбил Вишнёв Ваня;

К=разбил Кузин Коля;

С=разбил Симонов Саша.

Запишем ответ на языке алгебры логики:

Ваня: (ВT ¬К) – расследует I отдел.

Коля: (¬КT ¬С) – расследует II отдел.

Саша: (¬СT ¬В) – расследует III отдел.

Построим таблицу истинности:

I отдел II отдел IIIотдел
В К С ¬К ¬С ¬В ВT ¬К ¬КT ¬С ¬СT ¬В
1 1 1 1 1
1 1 1
1 1 1 1
1 1 1
1 1 1 1 1
1 1 1 1
1 1 1
1 1 1

Проанализировав таблицу истинности видно, что выражение истинно в двух случаях, 1. когда В=0, К=1 и С=0 и 2. когда В=1, К=0 и С=1. Но стекло разбил кто-то один.

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

6. Домашнее задание.

Дело о вымогательстве.

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

Брагин: “Я не участвовал в вымогательстве. Это делал Лиходеев”.

Лиходеев: “Я не виноват, но и Кургин тут ни причём”.

Кургин: “Лиходеев не виновен. Вымогательство совершал Брагин”.

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

Ребята, посчитайте количество звёзд на ваших погонах. Определите в каком звании вы находитесь. Используйте таблицу истинности.

кол-во звёзд кол-во звёзд > 2 кол-во звёзд >3 кол-во звёзд >4 конъюнкция дизъюнкция
2 и менее
3
4
5
6 и более

Ключ: если К=1 и Д =1, то “отличник”, отметка “5”;

если К=0 и Д=1, то “хорошист”, отметка “4”;

если К=0 и Д=0, то “плохиш”, отметка “3”.

Обучающиеся заполняют таблицу и в соответствии с ключом получают звания и отметки, учитель поздравляет с получением “званий” и выставляет соответствующие отметки в дневник.

Источник