Меню

Дискретная математика как построить таблицу истинности

Конспект лекции по дисциплине ЕН.02 Дискретная математика по теме 1.1 «Логические операции. Формулы логики. Таблица истинности»

Тема 1.1 Логические операции. Формулы логики. Таблица

истинности

Студент должен:

основные логические операции;

понятие формулы логики, понятие таблицы истинности формулы логики и методику ее построения, понятие тождественно-истинной формулы;

Формулы логики

Понятие высказывания

Высказывание – связное повествовательное предложение (утверждение), о котором можно сказать, истинно оно или ложно.

Меньше один в является два при.

Слава российским студентам!

Математика – интересный предмет.

Каша – вкусное блюдо.

Площадь комнаты равна 20м 2 .

В приведенных примерах 1,2,3 – истинные высказывания, а 4 – ложное высказывание. 5 и 7 не являются высказываниями, так как не являются повествовательными предложениями. А 6 не является высказыванием по причине не связности. 8 и 9 – не высказывания, так как нет и не может быть единого мнения о том, истинны эти предложения или ложны. 10 и 11 – не высказывания, так как необходимы дополнительные сведения: когда и где шел снег, о какой конкретной комнате идет речь. И 12 не высказывание, так как нельзя сказать истинно оно или ложно, пока мы не знаем чему равны X и Y .

В дальнейшем, если а – истинное высказывание, то будем писать символ “1”, если a — ложное высказывание, то будем писать символ “0”.

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

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

Отрицание.

Отрицание высказывания a – высказывание, истинное, когда высказывание a ложно и ложное – в противном случае.

Обозначение:, ¬а (читается: “не а”, “неверно, что а”)

Отрицание определяется следующей таблицей

а – “Идет дождь”

Конъюнкция.

Конъюнкцией двух высказываний a и b называется высказывание, истинное, когда оба высказывания истинны, и ложное – во всех других случаях.

Обозначение: a & b ; a ^ b ; a * b (читается: “ a и b ”). Конъюнкция определяется следующей таблицей:

a – “Небо покрыто тучами”

b “Идет дождь”

a & b – “Небо покрыто тучами и идет дождь”

Дизъюнкция.

Дизъюнкцией двух высказываний a и b называется высказывание, ложное в случае, когда оба высказывания ложны и истинное – во всех других случаях

Обозначение: ab (читается a или b ).

Дизъюнкция определяется таблицей:

a – “Идет дождь”

b “Идет снег”

a b – “Идет дождь или снег”

Импликация.

Импликацией двух высказываний a и b называется высказывание, ложное, когда a истинно, а b ложно; во всех других случаях – истинные.

Обозначение: a b (читается: “если a то b ”, “из a следует b ”)

Импликация определяется таблицей:

a – “Идет дождь”

b “Крыши мокрые”

a b – “Если идет дождь, то крыши мокрые”

Эквиваленция.

Эквиваленцией двух высказываний a и b называется высказывание, истинное, когда a и b имеют одинаковые значения истинности и ложное – в противном случае.

Обозначение: a

b (читается: “ a эквивалентно b ”, “ a тогда и только тогда, когда b ”).

Эквиваленция определяется таблицей:

a – “Идет дождь”

b “Крыши мокрые”

b – “Идет дождь тогда и только тогда, когда крыши мокрые”

Формулы логики.

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

Любая переменная, обозначающая высказывание – формула;

Если A и B – формулы, то , ( A & B ), ( A ∨ B ), ( A → B ), ( A

Других формул нет.

Порядок действий: ¬, &, ∨ , →,

(( a →) a)

((a 0)* a) →;

(c );

(→ x ∨)

1, 2 – формулы, 3, 4 не являются формулами.

Методика построения таблицы истинности.

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

При построении таблицы истинности наборы значений переменных располагают сверху вниз в порядке возрастания от (00…0) до (11…1). При этом можно применить метод ”последовательного половинного деления столбцов” – столбец первой переменной делят пополам и заполняют верхнюю половину нулями, а нижнюю половину – единицами, затем каждую половину второго столбца делят пополам и опять заполняют полученные половины нулями и единицами и т.д. Последовательность такого заполнения приведена ниже.

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

Пример. Построить таблицу истинности формулы:

Определим порядок действий в формуле:

2. Пользуясь определениями операций ¬, &, ∨ и → заполним таблицу.

Тождественно-истинной формулой называется формула, которая при любых значениях истинности своих простых высказываний принимает значение “истина”.

Задачи для самостоятельного решения

1. Какие из следующих предложений являются высказываниями:

а)Москва — столица России;

б) студент физико-математического факультета;

г) Луна есть спутник Марса;

2. Приведите примеры предложений, а) являющихся высказываниями; б) не являющихся высказываниями.

3. Среди следующих высказываний указать элементарные (простые) и составные (сложные). В составных высказываниях выделить грамматические связки:

1) число 27 не делится на 3;

2) число 15 делится на 5 и на 3;

3) если число 126 делится на 9, то оно делится на 3;

4) число 7 является делителем числа 42;

5) число 1269 делится на 9 тогда и только тг когда 18 делится на 9.

4. Обозначьте элементарные высказывания буквами и запишите следующие высказывания с помощью символов алгебры логики:

1) 45 кратно 3 и 42 кратно 3;

2) 45 кратно 3 и 12 не кратно 3;

4) если число 212 делится на 3 и 4, то оно делится 12;

5) число 212 — трехзначное и кратно 3 или 4.

6. Какие из следующих импликаций истинны:

1) если 2х2=4, то 2 3;

3) если 2х2=5, то 2 3?

7. Известно, что импликация х у истинна, а эквивалентность х у ложна. Что можно сказать о значении импликации у х ?

Контрольные вопросы

Что называется высказыванием?

Определения простого (элементарного) и сложного (составного) высказываний.

Логические значения высказываний.

Что называется отрицанием простого высказывания? Привести таблицу истинности.

Что называется дизъюнкцией двух простых высказываний? Привести таблицу истинности.

Что называется конъюнкцией двух простых высказываний? Привести таблицу истинности.

Что называется импликацией двух простых высказываний? Привести таблицу истинности.

Что называется эквиваленцией двух простых высказываний? Привести таблицу истинности.

Определение формулы алгебры логики.

Читайте также:  Как посмотреть кто просматривал гугл таблицу

В какой последовательности выполняются логические операции?

Источник



Построение таблиц истинности

Вы будете перенаправлены на Автор24

Логическая функция – функция, переменные которой принимают одно из двух значений: $1$ или $0$.

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

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

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

Готовые работы на аналогичную тему

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

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

Алгоритм построения таблицы истинности логической функции

Определяют количество строк: кол-во строк = $2^n + 1$ (для строки заголовка), $n$ – количество простых выражений. Например, для функций двух переменных существует $2^2 = 4$ комбинации наборов значений переменных, для функций трех переменных – $2^3 = 8$ и т.д.

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

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

Составить таблицу истинности логического выражения $D=\bar \vee (B \vee C)$.

Решение:

Определим количество строк:

Количество простых выражений – $n=3$, значит

кол-во строк = $2^3 + 1=9$.

Определим количество столбцов:

Количество переменных – $3$.

Количество логических операций и их последовательность:

Кол-во столбцов = $3 + 3=6$.

Заполним таблицу, учитывая таблицы истинности логических операций.

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

Решение:

Определим количество строк:

Количество простых выражений – $n=3$, значит

кол-во строк = $2^3 + 1=9$.

Определим количество столбцов:

Количество переменных – $3$.

Количество логических операций и их последовательность:

  1. отрицание ($\bar$);
  2. дизъюнкция, т.к. она находится в скобках ($A \vee B$);
  3. конъюнкция ($(A\vee B)\bigwedge \overline$);
  4. отрицание, которое обозначим $F_1$ ($\overline<(A\vee B)\bigwedge \overline>$);
  5. дизъюнкция ($A \vee C$);
  6. конъюнкция ($(A\vee C)\bigwedge B$);
  7. отрицание, которое обозначим $F_2$ ($\overline<(A\vee C)\bigwedge B>$);

Кол-во столбцов = $3 + 8 = 11$.

Заполним таблицу, учитывая таблицу истинности логических операций.

Алгоритм построения логической функции по ее таблице истинности

  1. Выделяют в таблице истинности строки со значением функции, равным $1$.
  2. Выписывают искомую формулу как дизъюнкцию нескольких логических выражений. Количество этих выражений равно количеству выделенных строк.
  3. Каждое логическое выражение в этой дизъюнкции записать как конъюнкцию аргументов функции.
  4. В случае, когда значение какого-то из аргументов функции в соответствующей строке таблицы принимает значение $0$, то этот аргумент записать в виде его отрицания.

По данной таблице истинности некоторой логической функции $Y(A,B)$ cоставить соответствующую логическую функцию.

Решение:

  1. Значение функции равно $1$ в $1$-й и $3$-й строках таблицы.
  2. Поскольку имеем $2$ строки, получим дизъюнкцию двух элементов:

  • Каждое логическое выражение в этой дизъюнкции запишем как конъюнкцию аргументов функции $A$ и $B$: $\left(A\wedge B\right)\vee \left(A\wedge B\right)$
  • В случае, когда значение в соответствующей строке таблицы равно $0$, запишем этот аргумент с отрицанием, получим искомую функцию:\[Y\left(A,B\right)=\left(\overline\wedge \overline\right)\vee \left(A\wedge \overline\right).\]
  • Источник

    Информатика

    План урока:

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

    Многие задачи можно решить, используя инструменты алгебры логики. Чтобы получить результат, можно пойти 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, которое используется с интерактивной доской.

    Источник

    Конспект лекции по дисциплине ЕН.02 Дискретная математика по теме 1.1 «Логические операции. Формулы логики. Таблица истинности»

    Тема 1.1 Логические операции. Формулы логики. Таблица

    истинности

    Студент должен:

    основные логические операции;

    понятие формулы логики, понятие таблицы истинности формулы логики и методику ее построения, понятие тождественно-истинной формулы;

    Формулы логики

    Понятие высказывания

    Высказывание – связное повествовательное предложение (утверждение), о котором можно сказать, истинно оно или ложно.

    Меньше один в является два при.

    Слава российским студентам!

    Математика – интересный предмет.

    Каша – вкусное блюдо.

    Площадь комнаты равна 20м 2 .

    В приведенных примерах 1,2,3 – истинные высказывания, а 4 – ложное высказывание. 5 и 7 не являются высказываниями, так как не являются повествовательными предложениями. А 6 не является высказыванием по причине не связности. 8 и 9 – не высказывания, так как нет и не может быть единого мнения о том, истинны эти предложения или ложны. 10 и 11 – не высказывания, так как необходимы дополнительные сведения: когда и где шел снег, о какой конкретной комнате идет речь. И 12 не высказывание, так как нельзя сказать истинно оно или ложно, пока мы не знаем чему равны X и Y .

    В дальнейшем, если а – истинное высказывание, то будем писать символ “1”, если a — ложное высказывание, то будем писать символ “0”.

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

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

    Отрицание.

    Отрицание высказывания a – высказывание, истинное, когда высказывание a ложно и ложное – в противном случае.

    Обозначение:, ¬а (читается: “не а”, “неверно, что а”)

    Отрицание определяется следующей таблицей

    а – “Идет дождь”

    Конъюнкция.

    Конъюнкцией двух высказываний a и b называется высказывание, истинное, когда оба высказывания истинны, и ложное – во всех других случаях.

    Обозначение: a & b ; a ^ b ; a * b (читается: “ a и b ”). Конъюнкция определяется следующей таблицей:

    a – “Небо покрыто тучами”

    b “Идет дождь”

    a & b – “Небо покрыто тучами и идет дождь”

    Дизъюнкция.

    Дизъюнкцией двух высказываний a и b называется высказывание, ложное в случае, когда оба высказывания ложны и истинное – во всех других случаях

    Обозначение: ab (читается a или b ).

    Дизъюнкция определяется таблицей:

    a – “Идет дождь”

    b “Идет снег”

    a b – “Идет дождь или снег”

    Импликация.

    Импликацией двух высказываний a и b называется высказывание, ложное, когда a истинно, а b ложно; во всех других случаях – истинные.

    Обозначение: a b (читается: “если a то b ”, “из a следует b ”)

    Импликация определяется таблицей:

    a – “Идет дождь”

    b “Крыши мокрые”

    a b – “Если идет дождь, то крыши мокрые”

    Эквиваленция.

    Эквиваленцией двух высказываний a и b называется высказывание, истинное, когда a и b имеют одинаковые значения истинности и ложное – в противном случае.

    Обозначение: a

    b (читается: “ a эквивалентно b ”, “ a тогда и только тогда, когда b ”).

    Эквиваленция определяется таблицей:

    a – “Идет дождь”

    b “Крыши мокрые”

    b – “Идет дождь тогда и только тогда, когда крыши мокрые”

    Формулы логики.

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

    Любая переменная, обозначающая высказывание – формула;

    Если A и B – формулы, то , ( A & B ), ( A ∨ B ), ( A → B ), ( A

    Других формул нет.

    Порядок действий: ¬, &, ∨ , →,

    (( a →) a)

    ((a 0)* a) →;

    (c );

    (→ x ∨)

    1, 2 – формулы, 3, 4 не являются формулами.

    Методика построения таблицы истинности.

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

    При построении таблицы истинности наборы значений переменных располагают сверху вниз в порядке возрастания от (00…0) до (11…1). При этом можно применить метод ”последовательного половинного деления столбцов” – столбец первой переменной делят пополам и заполняют верхнюю половину нулями, а нижнюю половину – единицами, затем каждую половину второго столбца делят пополам и опять заполняют полученные половины нулями и единицами и т.д. Последовательность такого заполнения приведена ниже.

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

    Пример. Построить таблицу истинности формулы:

    Определим порядок действий в формуле:

    2. Пользуясь определениями операций ¬, &, ∨ и → заполним таблицу.

    Тождественно-истинной формулой называется формула, которая при любых значениях истинности своих простых высказываний принимает значение “истина”.

    Задачи для самостоятельного решения

    1. Какие из следующих предложений являются высказываниями:

    а)Москва — столица России;

    б) студент физико-математического факультета;

    г) Луна есть спутник Марса;

    2. Приведите примеры предложений, а) являющихся высказываниями; б) не являющихся высказываниями.

    3. Среди следующих высказываний указать элементарные (простые) и составные (сложные). В составных высказываниях выделить грамматические связки:

    1) число 27 не делится на 3;

    2) число 15 делится на 5 и на 3;

    3) если число 126 делится на 9, то оно делится на 3;

    4) число 7 является делителем числа 42;

    5) число 1269 делится на 9 тогда и только тг когда 18 делится на 9.

    4. Обозначьте элементарные высказывания буквами и запишите следующие высказывания с помощью символов алгебры логики:

    1) 45 кратно 3 и 42 кратно 3;

    2) 45 кратно 3 и 12 не кратно 3;

    4) если число 212 делится на 3 и 4, то оно делится 12;

    5) число 212 — трехзначное и кратно 3 или 4.

    6. Какие из следующих импликаций истинны:

    1) если 2х2=4, то 2 3;

    3) если 2х2=5, то 2 3?

    7. Известно, что импликация х у истинна, а эквивалентность х у ложна. Что можно сказать о значении импликации у х ?

    Контрольные вопросы

    Что называется высказыванием?

    Определения простого (элементарного) и сложного (составного) высказываний.

    Логические значения высказываний.

    Что называется отрицанием простого высказывания? Привести таблицу истинности.

    Что называется дизъюнкцией двух простых высказываний? Привести таблицу истинности.

    Что называется конъюнкцией двух простых высказываний? Привести таблицу истинности.

    Что называется импликацией двух простых высказываний? Привести таблицу истинности.

    Что называется эквиваленцией двух простых высказываний? Привести таблицу истинности.

    Определение формулы алгебры логики.

    В какой последовательности выполняются логические операции?

    Источник

    Adblock
    detector