Меню

Тавтология доказательство при помощи таблицы истинности



Тавтология. доказательство при помощи таблицы истинности.

Понятие множества. Диаграммы Эйлера-Венна. Дополнение.

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

Диаграммы Эйлера-Венна используются для наглядного представления соотношения между несколькими подмножествами какого-либо универсума. (См. в тетради).

  • Множество элементов основного множества Е, не принадлежащих множеству А, называется дополнением множества А до множества Е или просто дополнением.

Высказывание. Элементарное высказывание. Основные операции (отрицание, конъюнкция, дизъюнкция, строгая дизъюнкция, импликация, эквиваленция).

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

Элементарное высказывание – одно утверждение.

  • Отрицанием высказывания Р называется высказывание, истинное тогда и только тогда, когда высказывание Р ложно.
  • Конъюнкцией двух высказывания П и К называется высказывание, истинное тогда и только тогда, когда истины оба высказывания.
  • Дизъюнкцией двух высказываний П и К называется высказывание, ложное тогда и только тогда, когда оба высказывания ложны.
  • Строгая дизъюнкция – высказывание П и К – «либо-либо», которое истинно тогда и только тогда, когда лишь одно из выражений истинно.
  • Импликацией двух высказываний П и К является высказывание, ложное тогда и только тогда, когда П истинно, а К ложно.
  • Эквиваленцией двух высказываний П и К называется высказывание, истинное тогда и только тогда, когда истистинностные значения П и К совпадают.

p>+ смотри в тетради.

Правильные рассуждения. Тавтология. Выполнимая формула. Тождественно ложная формула. Опровержимая формула.

Рассуждения являются правильными, если из конъюнкции начальных следует заключение, т.е посылка истинны заключаются истинно(р1, р2)-посылки. Д-заключение.

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

Совершенная дизъюнктивная нормальная форма.

В наборе элементов, где Булевы функции = истина. Если значение переменной = ложь, то эта переменная берётся с отрицанием. Если значение переменной = истина, то эта переменная берётся без отрицания. Соединив все переменные, соответствующие этому набору через знак конъюнкции, мы получим элементарную конъюнкцию. Тогда дизъюнкция всех элементарных конъюнкций, соответствующих набору значений переменных, где функция принимает значение истина и восстанавливает исходную функцию – это СДНФ нашей функции.

Совершенная конъюнктивная нормальная форма.

Обращаем внимание на набор переменных, при которых функция принимает значение ложь. Если в этот набор переменных входит с истистинностным значением ложь, то её берём без знака (чёрточка над буквой). Если она входит в истину, то её берём с этим знаком. Переменные внутри одного набора (+) и получают элементарную дизъюнкцию. Конъюнкция элементарных дизъюнкций и образует СКНФ.

Тавтология. Доказательство при помощи таблицы истинности.

Тавтология – это функция, которая на любых оценках списка переменных она принимает значение истины.

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

  • Логический закон: Закон тождества в правильном рассуждении = каждое высказывание тождественно самому себе.
  • Противоречие: 2 высказывания, которые отрицают, друг друга не могут быть вместе истинными.
  • Исключение третьего: 2 высказывания, которые отрицают, друг друга не могут быть вместе ложными, одно из них обязательно истинно, третье же исключено.
Читайте также:  Таблица менделеева как заставка

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

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

+ смотри в тетради.

Статьи к прочтению:

Братство Языка — Тавтология

Похожие статьи:

Таблицы сложения и умножения в восьмеричной системе 4 страница

6. Информатика. Базовый курс. / Под ред.Симоновича. – СПб., 2001. 7. Косарев В.П., Еремин Л.В. Компьютерные системы и сети. – М., 1999. 8. Дорот В.,…

Введение В предыдущей части статьи об управлении планировщиком заданий средствами командной строки вы узнали о фундаментальных отличиях планировщика…

Источник

Операции над высказываниями и предикатами. Таблицы истинности

п.1. Отрицание

Расшифровка первого правила: высказывание «неверно, что для любого x выполняется A(x)» совпадает с высказыванием «найдётся x, для которого A(x) не выполняется».
Расшифровка второго правила: высказывание «неверно, что найдётся x, для которого выполняется A(x)» совпадает с высказыванием «для любого x A(x) не выполняется».

п.2. Конъюнкция

Обозначение конъюнкции AB, читается «А и В». Таблица истинности:

С точки зрения операций над множествами, конъюнкция аналогична пересечению двух множеств (см. §10 справочника для 8 класса).

С точки зрения записи условий, конъюнкция аналогична системе с фигурной скобкой.

п.3. Дизъюнкция

Обозначение дизъюнкции AB, читается «А или В». Таблица истинности:

С точки зрения операций над множествами, дизъюнкция аналогична объединению двух множеств (см. §10 справочника для 8 класса).

С точки зрения записи условий, дизъюнкция аналогична совокупности с квадратной скобкой. Например, запись \(\mathrm<(x^2-1\geq 0)\vee \left(x\gt \frac12\right)>\) аналогична совокупности $$ \left[ \begin < l >\mathrm & \\ \mathrm & \end\right. \Leftrightarrow x\leq -1 \cup x\gt\frac12 $$

п.4. Импликация

Обозначение импликации AB, читается «если A, то B».
Высказывание A называют «посылкой», а высказывание B – «заключением».
Значение импликации зависит от порядка высказываний.
Таблица истинности:

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

Обозначение эквиваленции AB, читается «A то же самое, что B» или «A эквивалентно B».
Таблица истинности:

п.6. Законы де Моргана

Докажем эквивалентность с помощью таблиц истинности:

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

Докажем эквивалентность с помощью таблиц истинности:

Высказывания слева и справа эквивалентны.

Не путайте эквиваленцию и эквивалентность.
Эквиваленция – это логическая операция с 0 или 1 на выходе, в зависимости от исходных А и В.
Эквивалентность(равносильность) – это отношение, при котором эквиваленция A ↔ B истинна при всех значениях логических переменных на области определения. Тогда A ⇔ B (пишут также A=B, A≡B, A

B).
Если A ⇔ B, то каждое из предложений является и необходимым и достаточным условием для другого предложения; используются словосочетания «необходимо и достаточно», «равносильно».

п.7. Алгоритм доказательства эквивалентности высказываний с помощью таблиц истинности

Например:
Докажем следующее свойство:

Столбцы совпадают. Значит, формулы эквивалентны.
Что и требовалось доказать.

п.8. Тавтология

Таблица истинности для тавтологии даёт итоговый столбец, заполненный только единицами.

Например: \(\mathrm\)

«Быть иль не быть» — это тавтология.

п.9. Примеры

Пример 1. Для формулы P(x, y)=(∃x∀y)(A(x,y)∧B(x,y))
сформулируйте предложения A и B, при которых:

а) формула всегда истинна; б) формула всегда ложна.
a) A(x,y): квадрат числа x больше y
B(x,y): куб числа x больше y
Пусть x = |y + 1|. Тогда x 2 = (y + 1) 2 > y – истинно ∀y
x 3 = |y + 1| 3 > y – ∀y
Таким образом, мы нашли x, при котором A(x,y) ∧ B(x,y) = 1 для любого y, т.е.
P(x,y) = 1.

б) A(x,y): x больше y
B(x,y): x меньше y
A(x,y)∧B(x,y) = 0 – ложно для любого y, т.к. не существует x, который одновременно был бы больше и меньше y.
P(x,y) = 0.

Читайте также:  Таблицы рабкина номера таблиц

Источник

Составить таблицу истинности для высказывания и доказать тавтологию

п.1. Отрицание

Расшифровка первого правила: высказывание «неверно, что для любого x выполняется A(x)» совпадает с высказыванием «найдётся x, для которого A(x) не выполняется».
Расшифровка второго правила: высказывание «неверно, что найдётся x, для которого выполняется A(x)» совпадает с высказыванием «для любого x A(x) не выполняется».

п.2. Конъюнкция

Обозначение конъюнкции AB, читается «А и В». Таблица истинности:

С точки зрения операций над множествами, конъюнкция аналогична пересечению двух множеств (см. §10 справочника для 8 класса).

С точки зрения записи условий, конъюнкция аналогична системе с фигурной скобкой.

п.3. Дизъюнкция

Обозначение дизъюнкции AB, читается «А или В». Таблица истинности:

С точки зрения операций над множествами, дизъюнкция аналогична объединению двух множеств (см. §10 справочника для 8 класса).

С точки зрения записи условий, дизъюнкция аналогична совокупности с квадратной скобкой. Например, запись \(\mathrm<(x^2-1\geq 0)\vee \left(x\gt \frac12\right)>\) аналогична совокупности $$ \left[ \begin < l >\mathrm & \\ \mathrm & \end\right. \Leftrightarrow x\leq -1 \cup x\gt\frac12 $$

п.4. Импликация

Обозначение импликации AB, читается «если A, то B».
Высказывание A называют «посылкой», а высказывание B – «заключением».
Значение импликации зависит от порядка высказываний.
Таблица истинности:

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

Обозначение эквиваленции AB, читается «A то же самое, что B» или «A эквивалентно B».
Таблица истинности:

п.6. Законы де Моргана

Докажем эквивалентность с помощью таблиц истинности:

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

Докажем эквивалентность с помощью таблиц истинности:

Высказывания слева и справа эквивалентны.

Не путайте эквиваленцию и эквивалентность.
Эквиваленция – это логическая операция с 0 или 1 на выходе, в зависимости от исходных А и В.
Эквивалентность(равносильность) – это отношение, при котором эквиваленция A ↔ B истинна при всех значениях логических переменных на области определения. Тогда A ⇔ B (пишут также A=B, A≡B, A

B).
Если A ⇔ B, то каждое из предложений является и необходимым и достаточным условием для другого предложения; используются словосочетания «необходимо и достаточно», «равносильно».

п.7. Алгоритм доказательства эквивалентности высказываний с помощью таблиц истинности

Например:
Докажем следующее свойство:

Столбцы совпадают. Значит, формулы эквивалентны.
Что и требовалось доказать.

п.8. Тавтология

Таблица истинности для тавтологии даёт итоговый столбец, заполненный только единицами.

Например: \(\mathrm\)

«Быть иль не быть» — это тавтология.

п.9. Примеры

Пример 1. Для формулы P(x, y)=(∃x∀y)(A(x,y)∧B(x,y))
сформулируйте предложения A и B, при которых:

а) формула всегда истинна; б) формула всегда ложна.
a) A(x,y): квадрат числа x больше y
B(x,y): куб числа x больше y
Пусть x = |y + 1|. Тогда x 2 = (y + 1) 2 > y – истинно ∀y
x 3 = |y + 1| 3 > y – ∀y
Таким образом, мы нашли x, при котором A(x,y) ∧ B(x,y) = 1 для любого y, т.е.
P(x,y) = 1.

б) A(x,y): x больше y
B(x,y): x меньше y
A(x,y)∧B(x,y) = 0 – ложно для любого y, т.к. не существует x, который одновременно был бы больше и меньше y.
P(x,y) = 0.

Источник

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

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

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

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

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

Читайте также:  Html academy ответы на испытания таблица

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, что не соответствует второй строке таблицы.

Источник

Adblock
detector