Логика от греческого слова icon

Логика от греческого слова


Смотрите также:
Название науки происходит от греческого слова Logos речь, мысль, разум, слово...
Логика в образовании...
Иппическая тематика в казахской литературе...
Как наука изучает факты, закономерности и механизмы психики...
Прогрессивные производственные технологии...
«Каталоги и картотеки в школьной библиотеке» Каталог...
Строгий стиль в широком смысле этап развития древне-греческого искусства первой половины 5 века...
Лекция №1 Тема: «Историческое знание и наука»...
Курс лекций по анатомо-физиологическим основам фк и с часть Анатомия...
Решение задач и структурное программирование для разработка прикладных программ и создания...
Рабочая программа учебной дисциплины логика и теория аргументации для специальности 030602...
Рабочая программа учебной дисциплины логика и теория аргументации для специальности 030602...



Загрузка...
страницы:   1   2   3   4   5   6   7
скачать




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


Введение


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

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

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

Основоположником формальной логики является древнегреческий философ и логик Аристотель ( 384-322 г. до н.э.). Основными работами Аристотеля являются “Органон”, где включены категории, “Об истолковании”; “Аналитики: первая и вторая работа”; ”О софистических опровержениях”; ”Топика” и др.

Сам Аристотель свое логическое учение назвал “Аналитикой”. Аналитика – это наука о средствах установления объективной истинности, наука о доказательстве.

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

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

  1. Закон противоречия, т.е. невозможно, чтобы противоречащие утверждения были истинными по отношению к одному и тому же объекту. С помощью математической символики и правил, этот закон записывается:  для всякого не может быть одновременно истинным утверждение и отрицание того же .

  2. Закон исключенного третьего. Математический запись:  для всякого , истинно либо утверждение , либо отрицание того же .

  3. Закон силлогизма. Математический запись: если две импликации формы истины, то истинно должно быть и третья импликация.

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

Например:

1. Если ABCD – квадрат, то ABCD – ромб; если ABCD – ромб, то ABCD – параллелограмм; следовательно, если ABCD – квадрат, то ABCD – параллелограмм.

2. Если , то ; если , то ; следовательно, если , то .

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

Идею, о математизации логики в XVII-веке, высказал немецкий математик Лейбниц. Но свою идею, реализовать не смог.

Только в начале XIX-го века, стали активно применять математические методы в логике. Это случилась благодаря работе ирландского математика Дж. Буля (1815-1864). Его основные работы «математический анализ логики» и «исследование законов мышления». В трудах Дж. Буля и шотландского математика О. Де Моргана математическая логика сформировалась как своеобразная алгебра – алгебра логики, впоследствии названная также булевой алгеброй. Работы Дж. Буля развивал и обобщал, профессор казанского университета П.С.Порецкий и другие ученый из области алгебры логики.

В связи с тем, что в математической логике применяется символический язык, аналогичный математическому, она также называется символической логикой. Применение математическая символика и формул в логике привело к ее значительному развитию.

Как известно, разработанный Евклидом, аксиоматический метод в геометрии, долгие время считалась не превзойденными по строгости обоснования геометрии. А появление неевклидовой геометрии Лобачевского (1826), и чуть позже независимо от него неевклидовой геометрии венгерского математика Бойаи (1832), предложения которой не согласуются с привычными пространственными представлениями, выдвинула ряд сложных проблем (в первую очередь проблему непротиворечивости аксиоматики), исследование которых с помощью традиционной формальной логики было невозможно. Это обстоятельство стала главной причиной для дальнейшего развития математической логики, введения в нее новых идей и методов, разработки новых систем логических исчислений с целью удовлетворения существующей потребностей математики.

Новый этап в развитии математической логики связан, прежде всего, с именем немецкого математика Г. Фреге. В своих трудах Фреге впервые систематизировал исчисление высказываний, т.е. аксиоматически построил логики высказываний. В работе « основные законы арифметики», он построил первый в истории науки, формально логико-математическую систему, содержащую значительный часть арифметики.

В развитии математической логики и применении ее к теории математического доказательства приняли участие выдающиеся математики и логики конца XIX и XX в., в том числе Дж. Пеано, Б. Рассел, А. Уайтхед, А.М. Тьюринг, Я. Лукасевич, А. Тарский, Д. Гильберт, Г. Генцен, К. Гёдель, С.К. Клини, Э.Л. Пост, А. Чёрч, И.И. Жегалкин, А.Н. Колмогоров, П.С. Новиков, А.А. Марков, Е.А. Щегольков и др.

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

Изучение курса “начала математической логики” на отделениях информатики, математики и физики физико-математических факультетах педагогических вузов, усовершенствует профессиональную подготовку будущих учителей по соответствующему профилю обучения.

Данный курс включает следующие разделы:

  • алгебра высказываний;

  • исчисление высказываний;

  • алгебра предикатов.


Алгебра высказываний


Под высказыванием понимается любое осмысленное выражение, про которое можно сказать истинное оно или ложное. Высказывание не может быть одновременно и истина и ложь. Таким образом, алгебра высказываний делится на два класса:

  • Класс, включающий истинные высказывание;

  • Класс, включающий ложные высказывание.

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

Алфавитом алгебры высказываний называется множество вида

А = {P, Q, R, X, Y, Z, … , P1, Q1, … , , , V, , ~, и, л , (, ) }, где большими латинскими буквами обозначены конкретное высказывание, далее их назовем предметные переменные языка алгебра высказываний. При необходимости употребляется также индексы из множества натуральных чисел; символы «и», «л»-представляют соответственно «1», «0», и называются предметные константы языка алгебры высказываний; « , , V, , ~» символы логические операции языка и «(,)» вспомогательные символы.

Основные логические операции алгебры высказываний.

Пусть имеются два высказывания X и Y.

Определение 1. Конъюнкцией (логическое умножение) двух высказываний X и Y называется новое высказывание, обозначаемое X&Y или X ^ Y (читается и X и Y), которое истинно тогда и только тогда, когда оба высказывания X и Y одновременно истины и ложь в остальных случаях.

Определение 2. Дизъюнкцией (логическое сложение) двух высказываний X и Y называется новое высказывание, обозначаемое X Y (читается или X или Y), которое ложно тогда и только тогда, когда оба высказывания одновременно ложны и истинно в остальных случаях.

Определение 3. Импликацией двух высказываний X и Y называется новое высказывание, обозначаемое XY или (читается: если X то Y; из X следует Y; X влечёт за собой Y), которое ложно только в том случае, когда высказывание X истина и высказывание Y ложно; истинно в остальных случаях.

Определение 4. Отрицанием высказывания X называется новое высказывание, обозначаемое или (читается не X), которое истина тогда и только тогда, когда X – ложное и ложно когда X истинно.

Определение 5. Эквиваленцией двух высказываний X и Y называется новое высказывание, обозначаемое X~Y или (читается X тогда и только тогда, когда Y), которое истина тогда и только тогда, когда X и Y одновременно истинно или ложно и ложно в остальных случаях.

В виде таблицы, основные логические операции алгебры высказываний:

X

Y

XY

XY

XY

X

X~Y

и

и

И

и

и

л

И

и

л

Л

и

л

л

Л

л

и

Л

и

и

и

Л

л

л

Л

л

и

и

И


Индуктивное определение формулы логики высказывания


  1. Каждая предметная переменная и предметная константа является формулой алгебры высказываний;

  2. Если Х формула алгебры высказываний, то выражение (), также является формулой алгебры высказываний;

  3. Если X и Y формулы алгебры высказываний, то (X&Y), (XY), (XY), (X~Y) – тоже являются формулами алгебры высказываний;

  4. Никаких других формул кроме пунктов 1-3 не существует, т.е. всякое выражение является формулой алгебры высказываний, если оно получено с помощью пунктов 1-3.

В строгом смысле, каждая формула алгебры высказываний, включает внешние скобки. Приведем примеры формул в языке алгебре высказываний:

(((X & Y) & Z) T) – есть формула логики высказываний,

Х – не является формулой логики высказываний.


Соглашения:

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

  2. Операции конъюнкции будем опускать, т.е. в место X&Y или X^Y, будем записать XY.

  3. Приоритет логических операций располагаются следующим образом

, ^, v, ,~.


Индуктивное определение подформулы


  1. Подформулой элементарной формулы является сама формула.

  2. Если формула имеет вид , то её подформулой является она сама и любая подформула формулы Х.

  3. Если формула имеет вид ХY, Х Y, ХY, Х~Y, то подформулой их являются они сами и все подформулы формулы Х и Y.

Например, для формулы , подформулой являются: .


Истинностные значения формулы логики высказывания


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

Рассмотрим произвольный двоичный набор длины n, т.е. , где . На каждом из таких наборов, формула B принимает либо значение истинно, либо значение ложь. Она и называется истиностным значением формулы B, на данном наборе значений переменных.

Пример. , истиностные значений в виде таблицы имеет вид:

x

у





0

0

0

1

0

1

1

1

1

0

1

1

1

1

1

1


Классификация формулы алгебры высказываний


Определение 1. Формула В называется тавтологией (тождественно истиной или общезначимой), если на любом наборе значений переменных, она принимает значение истина.

Примерамb тавтологии являются:



Определение 2. Формула В называется тождественно ложной (противоречием или невыполнимой), если на любом наборе значений переменных, она принимает значение ложно.

Определение 3. Формула В называется выполнимой, если существует хотя бы один набор значений переменных, на котором формула В истина.
^

Важнейшие свойства общезначимых формул



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

10. Если общезначимая формула, то формула , получающаяся из формулы с помощью операции подстановки, также является общезначимая.

20. Если и общезначимые формулы, то формула , получающаяся из формулы и с помощью правилу заключения, также является общезначимая.

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


Понятие равносильности.

Основные равносильные формулы алгебры высказываний


Пусть А и В произвольные формулы алгебры высказываний и список переменных для этих формул.

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

А = В или А В.

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

Определение 5. Две формулы называется неравносильными, если существует хотя бы один набор из значений переменных, на котором они принимают различные значение.

Например, формулы , являются неравносильными. Действительно, на наборе они принимают разные значение.



Приведем перечень основных равносильных формул алгебры высказываний.



































С помощью основных равносильных формул можно осуществить равносильные преобразования формул.

Например, пусть и . Действительно, они являются равносильными. Одним из способов доказательства является следующие: если преобразовать формулы , с учетом таблицы равносильности формулы алгебры высказываний и при этом получить формулы , то мы получим, что и требовалась доказать.




Булевы функции


Рассмотрим функцию вида , где аргументы и сама функция принимает значения из множества {0,1} ({л, и}). Такие функции называются булевы функции.

По другому, булевы функция , сопоставляет всякому картежу длину из 0 и 1, значение 0 или 1, т.е. .

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

Теорема 1. Существует - булевы функции от переменных.


Доказательство. Пусть - произвольный двоичный набор, на каждом из которых функция , принимает значение 0 или 1. Как нам известно, количества таких наборов ровна . Всякому булевому функцию с каждым из таких наборов, соответствует одно из двух истинностных значений 0 или 1. Следовательно, булевы функции столько, сколько можно составит различных двоичных наборов. Но всякий такой набор есть размещения с повторения из 2 по , т.е. .

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

В виде таблицы это можно показать так:

х1, x2, … , xn

f(х1, x2, … , xn)

0, 0, … , 0

0, 0, … , 1

0, 0, … , 1, 1

… … …

1, 1, … , 1

f(0, 0, … , 0)

f(0, 0, … , 1)

f(0, 0, … , 1, 1)

… … …

f(1, 1, … , 1)


Возникает вопрос: «Существует ли формула с помощью которой можно задать булеву функцию?»

Введем обозначения:


Рассмотрим , при , возможны два случае: или . В обоих случаях мы получаем 1. Действительно, .

При , также возможны два случае: или . В обоих случаях мы получаем 0. Действительно, .

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

На практике часто при анализе и синтезе информационных систем, в том числе анализ и синтез контактных и электронных схем, на первом этапы исследования используются следующие булевы функции:







Совершенные нормальные формы булевы функций


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

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

Пусть булева функция задана в виде таблицы, т.е.









1

1

1

1

1

1

0

1

1

0

1

1

1

0

0

0

0

1

1

1

0

1

0

0

0

0

1

0

0

0

0

0

Способ 1. 1) Рассмотрим все те наборы значений переменных, для которых функция принимает значение «1».

2) Для каждого из отобранных наборов составляем конъюнкцию из переменных или их отрицаний (имеются виду те наборы, где функция принимает значение «1»).

Образующие конъюнкций (с отрицаниями или без них), называется элементарными конъюнкциями. В нашем случае, элементарными конъюнкциями являются следующие формулы:



3) На следующий шаг, составляем дизъюнкцию из имеющих элементарных конъюнкций, т.е.

.

Определение 1. Дизъюнкция, составленная из элементарных конъюнкций, называется совершенной дизъюнктивной нормальной формой (СДНФ).

Пусть задана местная булева функция, т.е. и также известно, что она на всяком двоичном наборе , принимает либо значение истинно (1), либо ложь(0).

Теорема 1. Всякая составленная СДНФ выражает ту же булеву функцию (истинностную функцию), что и истинностная таблица.

Доказательство. Пусть функция , согласно истинностной таблице на наборе , принимает значение 1, т.е. . Тогда этот набор будет находиться среди выбранных, значит среди составленных элементарный конъюнкций будет такая, которая при данном наборе принимает значение 1. Поэтому в СДНФ будет один член, имеющий значение 1. По определению дизъюнкции, значение 1 будет иметь и СДНФ.

Пусть теперь при данном наборе , согласно истинностей таблицы, функция принимает значение 0. Тогда этого набора не будет среди выбранных. Значит все составленные элементарные конъюнкции будут иметь значение 0. Следовательно, все члены СДНФ принимают значение 0.

Способ 2. Этот алгоритм, аналогичен первому способу, поэтому мы приведем его кратко без пояснений и доказательства.

1) Рассмотрим все те наборы значений переменных, для которых функция принимает значение «0».

2) Для каждого из отобранных наборов составляем дизъюнкцию из переменных или их отрицаний (имеются виду те наборы, где функция принимает значение «0»).

Образующие дизъюнкций (с отрицаниями или без них), называется элементарными дизъюнкциями. В нашем случае, элементарными дизъюнкциями являются следующие формулы:



3) На следующий шаг, составляем конъюнкцию из имеющих элементарных дизъюнкций, т.е.

.

Определение 2. Конъюнкция, составленная из элементарных дизъюнкций, называется совершенной конъюнктивной нормальной формой (СКНФ).

Теорема 2. Всякая составленная СКНФ выражает ту же булеву функцию (истинностную функцию), что и истинностная таблица.

Доказательство самостоятельно.

Следствие. Всякая булева функция, не принимающая значение 0, может быть представлена в виде СДНФ. Всякая булева функция, не принимающая значение 1, может быть представлена в виде СКНФ.

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

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

Пусть , тогда на любом наборе значений переменных, функция . Возьмем произвольный двоичный набор и определим множества вида . Тогда функцию , можно представить как СДНФ, т.е. , где для любого . По теореме 1, это утверждения верна. Таким образом, теорема доказано.

Следствие 1. Так как, конъюнкция может быть выражена через дизъюнкцию и отрицание, то всякую булеву функцию можно выразит с помощью .

Следствия 2. Так как, дизъюнкция может быть выражено через конъюнкцию и отрицание, то всякую булеву функцию можно выразит с помощью .

Правдоподобности эти утверждений, следуют из равносильности формулы алгебры высказываний:








оставить комментарий
страница1/7
Дата24.09.2011
Размер0.74 Mb.
ТипЗакон, Образовательные материалы
Добавить документ в свой блог или на сайт

страницы:   1   2   3   4   5   6   7
плохо
  1
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх