Сделай Сам Свою Работу на 5

Высказывания и операции над ними. Формулы





МАТЕМАТИЧЕСКАЯ ЛОГИКА

Введение

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

Математическая логика дала средства для построения логических теорий и вычислительный аппарат для решения задач. Математическая логика и теория алгоритмов нашли широкое применение в различных областях научных исследований и техники (например, в теории автоматов, в лингвистике, в теории релейно-контактных схем, в экономических исследованиях, в вычислительной технике, в информационных системах и др.). Основные понятия математической логики лежат в основе таких ее приложений, как базы данных, экспертные системы, системы логического программирования. Эти же понятия становятся методологической основой описания анализа и моделирования автоматизированных интегрированных производств.



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

 


Раздел I. АЛГЕБРА ВЫСКАЗЫВАНИЙ

Алгебру высказываний можно рассматривать как переложение на другой (алгебраический) язык результатов, изученных в разделе «Булевы функции», использующем функциональный язык. При функциональном подходе каждой из логических операций и формул сопоставляется определённая двузначная функция. При алгебраическом подходе логические операции интерпретируют как алгебраические, действующие на множестве двух элементов.



Высказывания и операции над ними. Формулы

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

Например, утверждение "2 > 0" является высказыванием и оно истинно, а утверждение "2 < 0" - ложно, утверждение "x2 + y2 = z2" высказыванием не является, так как оно может быть, как истинным, так и ложным при различных значениях переменных x, y, z. Высказывание полностью определяется своим истинностным значением. Условимся, значение истинности высказывания обозначать 1, если высказывание истинно, и 0, если высказывание ложно, что в точности соответствует значениям переменных булевых функций.

Различают высказывания простые и сложные, высказывание называется простым, если никакая его часть не является высказыванием. Простые высказывания будем обозначать начальными заглавными буквами латинского алфавита A, B, C или A1, A2, . . .. Сложные высказывания характеризуются тем, что образованы из нескольких простых высказываний с помощью логических операций, т.е. являются формулами алгебры высказываний.

Напомним, что алгебраической структурой или алгеброй называется структура, образованная некоторым множеством вместе с введенными на нём операциями. Определим алгебру высказываний.

Обозначим через B = {0, 1} – множество высказываний. Определим операции на множестве B.



Отрицанием высказывания A называется высказывание, которое принимает значение истина, если A ложно, и наоборот. Отрицание обозначается (ØА) и является унарной операцией.

Пусть А и В - некоторые элементарные высказывания, введем бинарные операции над ними.

Конъюнкцией высказываний A и B называется высказывание, которое принимает значение истина тогда и только тогда, когда истинны оба высказывания A и B. Обозначается конъюнкция - A B (А&В).

Дизъюнкцией высказываний A и B называется высказывание, которое принимает значение истина, если истинно хотя бы одно из высказываний A или B. Обозначается дизъюнкция - A B.

Импликацией высказываний A и B называется высказывание, которое принимает значение ложь тогда и только тогда, когда A истинно, а B ложно. Обозначается А®В.

Эквиваленцией высказываний A и B называется высказывание, которое принимает значение истина тогда и только тогда, когда высказывания A и B имеют одинаковые значения. Обозначение операции - А~В (АºВ).

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

 

A B ØA AÙB AÚB A®B A~B

Пропозициональной (высказывательной) переменной называется переменная, значениями которой являются простые высказывания. Обозначим высказывательные переменные через X1, X2, . . . , Xn.

Понятие формулы алгебры высказываний вводится по индукции. Формулами алгебры высказываний являются:

1) логические константы 0 и 1;

2) пропозициональные переменные;

3) если АиВ –формулы, то каждое из выражений Ø(А), (А)Ù (В), (А)Ú (В), (А)® (В), (А) ~ (В) есть формула;

4) других формул, кроме построенных по пп. 1) - 3), нет.

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

Для формулы построенной по п. 3 формулы Aи B называются подформулами. Число скобок в формуле можно сократить, Порядок выполнения операций в формуле определяется их приоритетом. Список логических операций в порядке убывания приоритета: ~. Изменение порядка выполнения операций, как и в алгебраических операциях, производится с помощью круглых скобок.

В соответствии с таблицами истинности операций можно построить таблицу истинности формулы. Для этого необходимо:

1. Пронумеровать простые высказывания в алфавитном порядке.

2. Для каждого элементарного высказывания рассмотреть все возможные наборы значений истинности. Всего возможно 2n комбинаций, где n - число элементарных высказываний. Это количество строк в таблице.

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

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

Задание. Построить таблицу истинности формулы

Ø(АÙВ) ® ØАÚС.

Решение.

1. Пронумеруем простые высказывания в алфавитном порядке А-1, В-2, С-3.

2. Каждый набор значений истинности элементарных высказываний изобразится набором 111, 110, 101 и т. д. Для нашего примера число комбинаций равно 8-ми, то есть таблица истинности будет содержать 8 строк.

3. Пронумеруем сложные высказывания формулы: АÙВ - 4; Ø(AÙB) - 5; ØA - 6; ØAÚС - 7; конечная операция ® - 8.

4. Вычислим последовательно значения истинности сложных высказываний.

 

 

Ø ( A Ù B ) ® Ø A Ú С

Формула называется выполнимой, если существует такой набор значений переменных, при которых эта формула принимает значение 1.

Формула называется опровержимой, если существует такой набор значений переменных, при которых эта формула принимает значение 0.

Формула называется тождественно истинной (ТИ-формулой) или тавтологией, если эта формула принимает значение 1 при всех наборах значений переменных.

Формула называется тождественно ложной (ТЛ-формулой) или противоречием, если эта формула принимает значение 0 при всех наборах значений переменных.

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

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.