Основные положения дискретной математики
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.
Формула А называется тождественно истинной, если на любом списке переменных она принимает значение «Истина».
Тавтология - это утверждение, которое всегда истинно, иначе ее определяют как закон.
Формула называется тождественно ложной, если на любом списке переменных она принимает значение «Ложь».
Противоречие - это утверждение, которое всегда ложно. Таблица истинности для противоречия всегда принимает значение «Ложь».
Например
А |
|||
И |
Л |
Л |
|
Л |
И |
Л |
Формула А называется выполнимой, если находится такой набор переменных, что она принимает значение «Истина».
Формула А называется опровержимой, если находится такой набор переменных, что она принимает значение «Ложь».
Что касается высказываний, то здесь применяется термин высказывание логически истинно, такое высказывание можно получить путем его подстановки в тавтологию (например: предложение «Если идет дождь или идет снег, и не идет дождь, то идет снег» получим путем подстановки в тавтологию и высказывание логически ложно, если его подставляют в противоречие.
Основные тавтологии
Доказательство утверждений
Для доказательства различных математических утверждений используются рассуждения, которые на языке логики могут быть выражены формулами