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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

ФИЛИАЛ

ФЕДЕРАЛЬНОГО ГОСУДАРСТВЕННОГО БЮДЖЕТНОГО ОБРАЗОВАТЕЛЬНОГО УЧРЕЖДЕНИЯ ВЫСШЕГО

ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«Московский технологический университет» в г. Ставрополе

Филиал МИРЭА в г. Ставрополе

Кафедра «автоматизированные системы управления»

Специальность 09.03.01 «Информатика и вычислительная техника»

КУРСОВАЯ РАБОТА

по дисциплине:

«Математическая логика и теория алгоритмов»

На тему: Логика высказываний и элементы теории алгоритмов

Вариант № 5

Выполнил:

Студент группы СВБО-01-15 ______________ Зыков Д.С.

(подпись)

Проверил:

Доцент, к.т.н. _______________ Авакян Т.А.

(подпись)

г. Ставрополь 2016г.

Содержание

1 Алгебра логики высказываний. 3

2 Построение таблицы истинности. 4

3 Дизъюктивная нормальная форма. 6

4 Конъюктивная нормальная форма. 7

5 Машина Тьюринга. 8

Список используемой литературы.. 10

Введение

АЛГЕБРА ЛОГИКИ ВЫСКАЗЫВАНИЙ

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

Базовыми элементами, которыми оперирует алгебра логики, являются высказывания.

Высказывание - это языковое образование, в отношении которого имеет смысл говорить о его истинности или ложности. Считается, что каждое высказывание либо истинно, либо ложно и ни одно высказывание не может быть одновременно истинным или ложным.

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

Логические операции – операции, выполняемые в соответствии с правилами булевой алгебры. К ним относят операции: отрицания, логическое «и», логическое «или» и тождество (эквивалентность). На этих логических операциях основана работа вычислительных машин. С помощью логических переменных и символов логических операций любое высказывание можно формализовать, то есть заменить логической формулой (логическим выражением).

Своим существованием наука «алгебра логики» обязана английскому математику Джорджу Булю, который исследовал логику высказываний.

Задание 1 Определите, истинно или ложно последнее высказывание, исходя из истинности или ложности предыдущих высказываний.

, , ;

Решение задачи

a	b	a	b	a˄b	a˅b	(a→b)˅a	(a→b)˅a	(a˄b)˅a)˄(a˅b)˅a

Ответ: исходя из условия эквивалентности, данное высказывание будет ложным.

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

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

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

1. Подсчитать количество переменных n.

2. Подсчитать количество строк m=2^n.

3. Количество столбцов = n+ количество логических операций.
Основные логические функции

Рисунок 2.1 – Конъюнкция

Рисунок 2.2- Дизъюнкция

Рисунок 2.3 – Инверсия

Рисунок 2.4 – Импликация

Рисунок 2.5 – Эквивалентность

Задание 2 Составьте таблицу истинности для формулы алгебры высказываний.

X ↔ ((Y ˅ Z) → (X ˅ Y))

Решение задачи

11) X↔((Y˅Z)→(X˅Y))

12) (X)↔((Y˅Z)→(X˅Y))