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

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

 

ФИЛИАЛ

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

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

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

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

 

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

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

 

 

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

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

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

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

Вариант № 5

Выполнил:

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

(подпись)

Проверил:

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

(подпись)

 

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

Содержание

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

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

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

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

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

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

 

 

Введение

 

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

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

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

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

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

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

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

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

, , ;

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

a	b	a	b	ab	ab	(ab)a	(ab)a	(ab)a)(ab)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((YZ)(XY))

12) (X)((YZ)(XY))