2.2. Логика высказывани и предикатов.

Логическое высказывание – связанное повествовательное предложение, о котором можно сказать истинно оно или ложно (На улице идёт дождь – высказывание, какая хорошая погода – не высказывание). В логике высказываний нас интересует не содержание, а истинностное значение высказываний (0 – Ложь, 1 – Истина).

Высказывания А и В равносильны тогда и только тогда, когда истинностные значения А и В совпадают ().

Основные операции над логическими высказываниями: (см. вопрос 2.1).

Логика предикатов – логическая система, средствами которой можно исследовать структуру высказываний.

Предикат – свойство объекта (отношения между объектами). Быть чётным, быть простым, делиться, быть больше.

–унарный.

–бинарный.

–трёхместный.

Предикат – функция, высказывательные переменные которой принимают значения из некоторого множества , а сама функция принимает значения {0; 1}.

Для задания предиката должно быть задано:

1. Область определения , состоящая из множества предметных переменных.

2. Множество – область значений предиката.

3. Правило, по которому каждому элементу из множества ставится в соответствие элемент из множества.

Способы задания предиката.

1. Графический.

2. Табличный

   	1	2	4	5
   	1	0	0	0

3. Словесный

Предикат выполняется при и не выполняется во всех остальных точкахx области определения.

4. Формульный (аналитический).

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

Кванторы.

1. Квантор общности. . Пусть – некоторый предикат, под выражениембудем подразумевать высказывание, истинное когдаистина для любогоиз множестваи ложное в противоположном случае.

2. Квантор существования. . Пусть– некоторый предикат, под выражениембудем подразумевать высказывание, истинное когда существует элемент из множества, для которогоистинно и ложное в противоположном случае..Существует такое x, которое кратно 2 и кратно 3.

Операции, уменьшающие местность предиката.

1. Фиксация значений переменной.

2. Операция связывания квантором

Обобщение логических операций с помощью квантора.

Пусть – одноместный предикат, который определён на конечном множестве.. Квантор общности определяет операцию конъюнкция.

Квантор существования обобщает операцию дизъюнкция.

Основные равносильности алгебры предикатов, содержащие кванторы.

1. Законы де Моргана. ,(перенос отрицания).

2. Перестановка одноимённых кванторов (коммунитативные законы). ,.

3. Дистрибутивные законы. ,

4. Законы ограничения действия кванторов ,,,.

Все законы, которые работают в алгебре высказываний, переносятся в алгебру предикатов.

3. Интуитивное и формальное определение алгоритма.

Алгоритм – эффективная процедура, однозначно приводящая к результату.

Основные требования к алгоритму:

• Каждый алгоритм должен иметь данные: входные, выходные, промежуточные

• Данные для своего размещения требуют памяти внутренней и внешней

• Алгоритм состоит из отдельных элементарных шагов, количество которых конечно

• Последовательность шагов алгоритма детерминирована, т.е. после каждого шага либо указывается какой шаг делать дальше либо дается команда остановки

• Результативность – остановка после конечного числа шагов, с указанием того, что считать результатом

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

Основные типы алгоритмических моделей:

1. Рекурсивные функции – вычисление и числовые функции

2. Машина Тьюринга – в основе лежит представление об алгоритме как некотором детерминированном устройстве, способном выполнить в каждый отдельный момент времени лишь примитивные операции

3. Каноническая система Поста и нормальные алгоритмы Маркова – происходит преобразование слов в произвольных алфавитах, в которых элементарные операции – это подстановки, т.е. замены части слова другим словом.

Пример: Машина Тьюринга

Машина Тьюринга состоит из 3-х частей:

1) Устройство управления, которое может находиться в одном из следующих состояний: Q = {q₁, q₂, …, q_n}.

2) Лента, которая разбита на ячейки, в каждой из которых может быть записан один из символов конечного алфавита A = {a₁, a₂, …, a_n}.

3) Устройство обращения к ленте, которая представляет из себя считывающую и пишущую головку. В каждый момент времени она обозревает ячейку ленты и в зависимости от символа на ленте и состоянию устройств управления, записывает в ячейку символ, который может быть пустым, т.е. стирает содержимое, сдвигается на ячейку влево или вправо, или остается на месте. После этого устройство управления переходит в новое состояние или остается в старом.

Среди состояний устройства управлений выделяют начальное – q₁ (оно существует перед началом работы) и выделяется заключительное состояние – q_z, после этого состояния машина Тьюринга останавливается.

Три способа описания:

1. Система команд

2. Таблица переходов: строки таблицы – состояния, столбцы – входные символы

3. Блок – схемы (диаграмма переходов)