Решение. «Элементы математической логики»

Цикл задач по теме

«Элементы математической логики»

Образец решения.

1. Составьте таблицу истинности для высказывания: ( );

Решение.

Таблица истинности имеет вид:

				( )
и	и	л	л	и
и	л	л	и	и
л	и	и	и	и
л	л	и	л	л

2. Докажите закон ассоциативности дизъюнкции;

Решение.

Ассоциативность дизъюнкции можно доказать составлением таблицы истинности:

				()		()
и	и	и	и	и	и	и
и	и	л	и	и	и	и
и	л	и	и	и	и	и
и	л	л	и	и	л	и
л	и	и	и	и	и	и
л	и	л	и	и	и	и
л	л	и	л	и	и	и
л	л	л	л	л	л	л
				--------		--------

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

3. Докажите равносильность формул двумя способами:

= ;

Решение.

Равносильность формул логики можно доказать составлением таблицы истинности:

и	и	и	л	л	л	л	и	и	и
и	и	л	л	л	и	и	и	л	и
и	л	и	л	и	л	и	и	л	и
и	л	л	л	и	и	и	и	л	и
л	и	и	и	л	л	л	л	и	л
л	и	л	и	л	и	и	и	л	и
л	л	и	и	и	л	и	и	л	и
л	л	л	и	и	и	и	и	л	и
							-------		------

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

Можно равносильность формул доказать, используя известные законы логики:

= ( )=	использовали замену импликации дизъюнкцией отрицания первого компонента и второго: q = q; и закон двойного отрицания
= =	использовали коммутативность и ассоциативность дизъюнкции
= =	использовали закон де Моргана и формулу: q = q

4. Докажите эквивалентность двух высказываний: и ;