Основные положения дискретной математики

лекция

4.3 Доказательство равносильностей

Доказательство равносильностей можно осуществить двумя способами:

с помощью таблицы истинности;

с помощью рассуждений.

Пример (Задание №6): докажем равносильность

а) с помощью таблицы.

Таб. 6

X

Y

Z

1

2

3

4

5

6

7

8

0

0

0

0

0

0

0

0

0

0

1

0

0

0

1

0

0

1

0

0

0

1

0

0

0

1

1

1

1

1

1

1

1

0

0

0

1

1

1

1

1

0

1

0

1

1

1

1

1

1

0

0

1

1

1

1

1

1

1

1

1

1

1

1

Мы видим в 5-ом и 8-ом столбцах получили одинаковые значения, тем самым мы доказали равносильность данной формулы.

б) с помощью рассуждений.

допустим истинность левой части

установим истинное значение для всех истинностных переменных, входящих в список или оценку списка

оценку списка подставим в правую часть равносильности

установим истинность для правой части

все повторим справа налево.

I.

х=И или И

если х=И И, И,

если и z = И

II.

и

х =И или y =И и х=И или z=И

если х=И И

если y=И и z=И =И

(И - «истина», т. е. присваивается истинное значение)

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

Правила перехода от одних равносильностей к другим

Пусть , а С - произвольная формула

С АС В

Правила равносильных преобразований

Пусть , а С - произвольная формула. Пусть х - формула, которая входит в С. тогда Са - формула, которая получается заменой в формуле С формулы х на а.Сb - получается из С заменой x на b, тогда Са=Сb.

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

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

Пусть f и g - функции алгебры логики, x1,…,xn - совокупность аргументов, входящих хотя бы в одну из этих функций, говорят, что f и g- равносильны, если при всех значениях x1,…,xn значения f и g - совпадают.

Тавтологии

Дана формула А х1 х2 х3.

Формула А называется тождественно истинной, если на любом списке переменных она принимает значение «Истина».

Тавтология - это утверждение, которое всегда истинно, иначе ее определяют как закон.

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

Противоречие - это утверждение, которое всегда ложно. Таблица истинности для противоречия всегда принимает значение «Ложь».

Например

А

И

Л

Л

Л

И

Л

Формула А называется выполнимой, если находится такой набор переменных, что она принимает значение «Истина».

Формула А называется опровержимой, если находится такой набор переменных, что она принимает значение «Ложь».

Что касается высказываний, то здесь применяется термин высказывание логически истинно, такое высказывание можно получить путем его подстановки в тавтологию (например: предложение «Если идет дождь или идет снег, и не идет дождь, то идет снег» получим путем подстановки в тавтологию и высказывание логически ложно, если его подставляют в противоречие.

Основные тавтологии

Доказательство утверждений

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

Делись добром ;)