birmaga.ru
добавить свой файл

1 2 3
1.Понятие множества, отображения, функции, логической функции, булевой функции.

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

Множества обозначаются прописными буквами латинского или готического алфавита: A, B, ...,M, K,... .

Если множество A состоит из элементов a,b,c,..., это обозначается с помощью фигурных скобок: A={a,b,c,...,} .

Множества, элементами которых являются числа называются числовыми:

N – множество всех натуральных чисел;

Zc (или Z+ или C+) – множество всех целых неотрицательных чисел;

Z (или C) – множество всех целых чисел;

Q – множество всех рациональных чисел;

R – множество всех действительных чисел;

R+ - множество всех действительных положительных чисел
По числу элементов, входящих в множество, множества делятся на три класса:

1. Если элементы множества можно сосчитать, то множество является КОНЕЧНЫМ

2. Если элементы множества сосчитать невозможно, то множество БЕСКОНЕЧНОЕ.

3.Множество, не содержащее ни одного элемента, называется ПУСТЫМ. Символически оно обозначается знаком .

Способы задания множеств.

Множество считается заданным, если мы владеем способом, позволяющим для любого данного элемента определить, принадлежит он данному множеству или не принадлежит.

Множество можно задать, непосредственно перечислив все его элементы, причём, порядок следования элементов может быть произвольным. В этом случае названия всех элементов множества записываются в строчку, отделяются точкой с запятой и заключаются в фигурные скобки.Множество всех гласных букв русского алфавита: A={а; я; у; ю; э; е;о; ё; и; ы}.

Конечные и бесконечные множества могут быть заданы другим способом: указанием ХАРАКТЕРИСТИЧЕСКОГО СВОЙСТВА, т.е. такого свойства, которым обладает любой элемент данного множества и не обладает ни один элемент, не принадлежащий ему.


Отношения между множествами.

Наглядно отношения между множествами изображают при помощи особых чертежей, называемых КРУГАМИ ЭЙЛЕРА (или диаграммами Эйлера – Венна).Для этого множества, сколько бы они ни содержали элементов, представляют в виде кругов или любых других замкнутых кривых

Множество В является подмножеством множества А тогда и только тогда, когда каждый элемент множества В является элементом множества А.

Множества C и D называются равными тогда и только тогда, когда множество С является подмножеством множества D, и наоборот.

Операции над множествами:

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

1.Объединением двух множеств А и В называется множество С , которое состоит из элементов множеств А и В



2.Пересечением двух множеств А и В называется множество С , которое состоит из общих элементов множеств А и В



3.Разностью двух множеств А и В (А-В) , называется множество С , которое состоит из элементов множества А , которых нет в множестве В



4.Симметрической разностью двух множеств А и В называется множество С , которое состоит из не общих элементов множеств А и В


Отображение (матем.) множества А в множество В, соответствие, в силу которого каждому элементу х множества А соответствует определённый элемент у = f (x) множества В, называют образом элемента х (элемент х называют прообразом элемента у).

Отображением множества E в множество F, или функцией, определенной на E со значениями в F, называется правило, или закон f, который каждому элементу ставит в соответствие определенный элемент .

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

Логический элемент - это устройство, реализующее ту или иную логическую функцию.

Y=f(X1,X2,X3,...,Xn) - логическая функция, она может быть задана таблицей, которая называется таблицей истинности.

Число строк в таблице - это число возможных наборов значений аргументов. Оно равно 2n, где n - число переменных.Число различных функций n переменных равно 2^2^n.

Бу́лева фу́нкция (или логи́ческая функция, или функция а́лгебры ло́гики) от n переменных — в дискретной математике отображение Bn → B, где B = {0,1} — булево множество. Элементы булева множества 1 и 0 обычно интерпретируют как логические значения «истинно» и «ложно».
Булевы свойства операций над множествами:

1. Идемпотентность (A и A) =A, (A или A)=A.

Термин идемпотентность означает свойство чего либо (объекта) которое проявляется в том, что повторное действие над объектом не изменяет его

2. Коммутативность (A и B) = (B и A), (A или B) = (B или A).

Свойство состоящее в том, что результат применения данной операции к предметам а и b, взятым в одном порядке, совпадает с результатом применения той же операции к тем же предметам, взятым в обратном порядке

3. Ассоциативность A и (B и C) = (A и B) и C, A или (B или C)=(A или B) или C.



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

4. Правило поглощения A и (A или B)=A, A или (A и B) = A.

одна переменная поглощает другие

5. Дистрибутивность - свойство согласованности двух бинарных операций, определённых на одном и том же множестве.Две бинарные операции + и × удовлетворяют свойству дистрибутивности, если для любых трех элементов x y z :






6. Инволюция не (не(A))=A.

Преобразование, которое является обратным самому себе.

7. Свойство констант (A и U) = A, (A или U) = U, (A и пустое множество) = пустое множество, (А или пустое множество) = A.

8. Закон исключённого третьего и закон противоречия (A или не(A)) = U, (A и не(A)) = пустое множество.

9. Не (А и В) = (не (А) или не (В)), не (А и В) = (не (А) или не (В)).

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


х

f1(x)

f2(x)

f3(x)

F4(x)

0

1

1

0

0

1

1

0

1

0

Из этой таблицы следует, что две функции являются константами f1(x) = 1 и – f2(x) = x, а остальные f3(x) =  x и f4(x) = 0.

основной задачей теории булевых функций является разработка систематического метода построения сложных функций из более простых
2.Булева алгебра. Функции многих переменных.
БУЛЕВА АЛГЕБРА, область математики, содержащая правила обращения с множествами, а также с логическими утверждениями типа «и», «или».



Функция п переменных – это отображение Еп в Е, которое можно задать непосредственно таблицей, называемой таблицей истинности данной функции.
Функции двух переменных z = f(x,y).



Две из них f0 = 0 и f15 = 1 являются константами.
функциями одной переменной.

-конъюнкция (функция И)

-дизъюнкция (функция или)

-импликация (следование)

-сложение по модулю 2

-эквивалентность или подобие

-штрих Шеффера

-стрелка Пирса


3.Высказывания. Исчисление высказываний. Логические связки и операции. 4.Законы логики. Основные эквивалентности.
Второй вариант применения булевой алгебры - логические рассуждения, высказывания.

Здесь два объекта интерпретируются как истина (будем обозначать как true) и ложь (будем обозначать как false). Далее мы будем называть символы true и false булевыми величинами, а переменные, которые их обозначают - булевыми переменными.

Обычно элементарные высказывания обозначают строчными буквами латинского алфавита a, b, c, x, y …, которые также являются логическими переменными.
Из элементарных высказываний можно составить более сложные с помощью логических связок , , , , , называемых соответственно отрицание, логическое и (конъюнкция), логическое или (дизъюнкция), логическое следствие (импликация), эквивалентность и круглых скобок (, ). Семантику логических связок можно представить с помощью таблицы истинности. В левой части этой таблицы перечисляются все возможные комбинации значений логических переменных.
Виды высказываний

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

Логическая связка — это любая логическая операция над высказыванием. Например, употребляемые в обычной речи слова и словосочетания «не», «и», «или», «если… , то», «тогда и только тогда» являются логическими связками.
Основные операции над логическими высказываниями

Отрицание логического высказывания — логическое высказывание, принимающее значение «истинно», если исходное высказывание ложно, и наоборот.

Конъюнкция двух логических высказываний — логическое высказывание, истинное только тогда, когда они одновременно истинны.

Дизъюнкция двух логических высказываний — логическое высказывание, истинное только тогда, когда хотя бы одно из них истинно.


Импликация двух логических высказываний A и B — логическое высказывание, ложное только тогда, когда B ложно, а A истинно.

Равносильность (эквивалентность) двух логических высказываний — логическое высказывание, истинное только тогда, когда они одновременно истинны или ложны.
Логика высказываний (или пропозициональная логика от англ. propositional logic) — это формальная теория, основным объектом которой служит понятие логического высказывания.
В алгебре логики имеется ряд законов, позволяющих производить равносильные преобразования логических выражений. Приведем соотношения, отражающие эти законы.

1. Закон двойного отрицания:

А = .

2. Переместительный (коммутативный) закон:

— для логического сложения:

A V B = B V A

— для логического умножения:

A&B = B&A.

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

3. Сочетательный (ассоциативный) закон:

— для логического сложения:

(A Ú B) Ú C = A Ú (BÚ C);

— для логического умножения:

(A&B)&C = A&(B&C).

4. Распределительный (дистрибутивный) закон:

— для логического сложения:

(A Ú B)&C = (A&C) Ú (B&C);

— для логического умножения:

(A&B) Ú C = (A Ú C)&(B Ú C).

5. Закон общей инверсии (законы де Моргана):

— для логического сложения

=& ;

— для логического умножения:

= Ú


6. Закон идемпотентности

— для логического сложения:

A Ú A = A;

— для логического умножения:

A&A = A.

7. Законы исключения констант:

— для логического сложения:

A Ú 1 = 1, A Ú 0 = A;

— для логического умножения:

A&1 = A, A&0 = 0.

8. Закон противоречия:

A& = 0.

9. Закон исключения третьего:

A Ú = 1.

10. Закон поглощения:

— для логического сложения:

A Ú (A&B) = A;

— для логического умножения:

A&(A Ú B) = A.

11. Закон исключения (склеивания):

— для логического сложения:

(A&B) Ú ( &B) = B;

— для логического умножения:

(A Ú B)&( Ú B) = B.

12. Закон контрапозиции (правило перевертывания):

(A Û B) = (BÛ A).

┐(А→В) = А&┐В

┐А&(АÚВ)= ┐А&В

АÚ┐А&В=АÚВ
Основные свойства алгебры логики позволяют осуществлять эквивалентные преобразования логических формул для их упрощения или приведения к требуемому виду, а также для доказательства логических правил и теорем.

В алгебре логики определено отношение эквивалентности (=), которое удовлетворяет следующим свойствам:

Х = Х - рефлексивность;

если X = Y, то Y = X - симметричность;

если X = Y, Y = Z, то X = Z - транзитивность.

Из отношения эквивалентности следует принцип подстановки: если X = Y, то в любой формуле, содержащей X, вместо X можно подставить Y и будет получена эквивалентная формула.

Эквивалентности:

X + 0 = X

X + 1 = 1

X + X = X

X + = 1


X 0 = 0

X 0 = X

X X = X

X = 0
5.Основная теорема булевой алгебры. СКНФ, СДНФ, ДНФ, КНФ
Любая двоичная функция может быть представлена как суперпози-ция только трех функций: И, ИЛИ и НЕ.

Любую логическую (булеву) функцию можно выразить через три логические функции: конъюнкцию, дизъюнкцию и отрицание.
Определение 1: Конъюнкцией(или логическое умножение) двух булевых переменных называется следующая функция.
Определение 2: Дизъюнкцией(логическое сложение) двух булевых переменных называется следующая функция.
Дизъюнктивная нормальная форма(ДНФ)
Дизъюнкция конечного множества элементарных конъюнкций называется дизъюнктивной нормальной формой(ДНФ). Число элементарных конъюнкций, образующих дизъюнктивную нормальную форму(ДНФ) называется длиной ДНФ. ДНФ содержащая только полные элементарные конъюнкции называется совершенной ДНФ(или СДНФ). Любую логическую формулу А можно представить в виде ДНФ, а затем ДНФ в виде СДНФ.
Алгоритм построения СДНФ:

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

Очевидно, для любой булевой функции , кроме константы 0, существует единственная СДНФ (с точностью до порядка литералов и конъюнкций). Поэтому данная форма представления булевой функции является канонической.

Конъюнктивная нормальная форма(КНФ)
Конъюнкция конечного множества элементарных дизъюнкций называется конъюнктивной нормальной формой(или сокращенно КНФ). Число элементарных дизъюнкций образующих КНФ называется длинной. КНФ состоящая только из полных элементарных дизъюнкций называется СКНФ. Произвольную формулу B vможно представить в виде КНФ, а затем КНФ в виде СКНФ.

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

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

7.Алгебра Жегалкина. Теорема о представлении функции единственным многочленом Жегалкина

8.Классы функций. Теорема о полноте.
Система функций {f1…fn} называется полной, если любую булеву функцию можно представить в виде суперпозиции функций из этой системы (т.е. можно представить формулой, куда входят только функции из этой системы).

Теорема:

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


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

специальная алгебра где

В алгебре Жегалкина выполняются следующие соотношения:

1. x y = y x;

2. x ( y z ) = x y x z;

3. x x = 0;

4. x = 1;

5. x 0 = x.

Полином Жегалкина - еще один способ выразить произвольную булеву функцию через бинарные операции.

Теорема.

Любая функция п переменных может быть представлена полиномом Жегалкина и это представление единственно.

x y = x y (x & y)


~x = x 1

Применив эти формулы, мы всякую булеву функцию выразим через операции & и .

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

Перечислим предполные классы булевых функций:

булевы функции, сохраняющие константу 0;

булевы функции, сохраняющие константу 1;

самодвойственные булевы функции;

линейные булевы функции;

монотонные булевы функции;
К булевым функциям сохраняющим константу 0, относят такие булеы функции f(x1,...,xn), для которых справедливо соотношение f(0,...,0)=0



К булевым функциям сохраняющим константу 1, относят такие булеы функции f(x1,...,xn), для которых справедливо соотношение f(1,...,1)=1.


Булевы функции f1(x1,...,xn) и f2(x1,...,xn) называются двойственными друг другу, если выполняется соотношение

f1(x1,...,xn)=/(f2(/x1,...,/xn))

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



К линейным булевым функциям относят такие булевы функции, которые представимы в виде полинома первой степени, т.е.



Это - такая логическая функция, которую можно выразить через , 0 и 1.


Булева функция f(x1,...,xn) называется монотонной, если для любых двух наборов Y = и B = таких, что Y >= B имеет место неравенство f(y1,...,yn)>=f(b1,...,bn).

Это - такая логическая функция, которую можно выразить через & и .





Теорема Поста:

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

10.Эквивалентные соотношения в исчислении предикатов.

Предика́т (лат. praedicatum — заявленное, упомянутое, сказанное) — любое математическое высказывание о некоторой функции, в котором есть, по меньшей мере, одна переменная.

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

Логические операции:

Конъюнкцией двух предикатов А(х) и В(х) называется новый предикат , который принимает значение «истина» при тех и только тех значениях х Т, при которых каждый из предикатов принимает значение «истина», и принимает значение «ложь» во всех остальных случаях.

Дизъюнкцией двух предикатов А(х) и В(х) называется новый предикат , который принимает значение «ложь» при тех и только тех значениях х Т, при которых каждый из предикатов принимает значение «ложь» и принимает значение «истина» во всех остальных случаях.
Отрицанием предиката А(х) называется новый предикат , который принимает значение «истина» при всех значениях х Т, при которых предикат А(х) принимает значение «ложь», и принимает значение «ложь», если А(х) принимает значение «истина»
Импликацией предикатов А(х) и В(х) называется новый предикат А(х) В(х), который является ложным при тех и только тех значениях х Т, при которых А(х) принимает значение «истина», а В(х) – значение «ложь» и принимает значение «истина» во всех остальных случаях

Кванторные операции

Кванторы - логические операции, с помощью которых по некоторому высказыванию А(х) получают новые высказывания, характеризующие область истинности высказывания А(х).
Квантор всеобщности — это условие, которое верно для всех обозначенных элементов, в отличие от квантора существования, где условие верно только для каких-то отдельных из указанных чисел.

обозначение -

Квантор существования — это предикат свойства или отношения для, по крайней мере, одного элемента области определения. (Квантор существования отличается от квантора всеобщности, который утверждает, что свойство или отношение выполняется для всех элементов области.)


обозначение -
Связь кванторов с операциями алгебры высказываний

Если , то






Основные аксиомы предикатов:

1. Аксиома двойного отрицания:



2. Аксиомы переместительности операндов (относительно операций дизъюнкции и конъюнкции):


3. Аксиомы переместительности операций дизъюнкции и конъюнкции (относительно операндов):




4. Аксиомы одинаковых операндов:



5. Аксиомы поглощения (множителем — множителя-суммы или слагаемым — слагаемого-произведения):



6. Аксиомы распределения операции (дизъюнкции относительно конъюнкции и наоборот):



7. Аксиомы де Моргана (перенесения бинарной операции на операнды):



8. Аксиомы нейтральности (взаимноинверсных множителей или слагаемых):



9. Аксиома существования единицы (истина, true, 1) и нуля (ложь, false, 0), причем,


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

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

-Все переменные, входящие в атомарную формулу, являются свободными переменными этой формулы,

-свободные переменные формулы F являются свободными переменными формулы ¬F,

-переменные, являющиеся свободными для хотя бы одной из формул F или G, являются свободными переменными формулы (F Д G),

-все свободные переменные формулы F кроме v являются свободными переменными формулы Kv F.
Замкнутая формула -формула без свободных переменных называется замкнутой формулой, или предложением.
Связанная переменная -переменная v связана в формуле F, если F содержит вхождение Kv, где K — квантор.
В логике (алгебре) предикатов справедливы все эквивалентные соотношения логики (алгебры) высказываний, а также собственные эквивалентные соотношения:


11.Логический вывод и метод резолюций. Примеры.

12.Дизъюнкты Хорна, фразы и резолюции. Примеры.

13.Правила унификаций в методе резолюций.
Вывод в формальной логической системе является процедурой, которая из заданной группы выражений выводит отличное от заданных семантически правильное выражение
Пра́вило резолю́ций — это правило вывода, восходящее к методу доказательства теорем через поиск противоречий; используется в логике высказываний и логике предикатов первого порядка.

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



ведется методом от противного. Для этого в исходное множество предложений включают аксиомы формальной системы и отрицание доказываемой гипотезы:



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

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

клаузальную форму – разновидность конъюнктивной нормальной формы (КНФ), в которой удалены кванторы существования, всеобщности, символы импликации, равнозначности и др.

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

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



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

Если S содержит пустое предложение , то S противоречиво (невыполнимо). Если предложение не является пустым, то делается попытка вывода предложений пока не будет получено пустое (что всегда будет иметь место для невыполнимого S).

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


Алгоритм унификации : чтобы унифицировать два различных выражения, отыскивается наиболее общий унификатор – НОУ (подстановка, при которой выражение с большей описательной мощностью согласуется с выражением, имеющим малую описательную мощность)
Пример: вывод решения в логической модели на основе метода резолюций.

Даны утверждения:

«Сократ – человек»;

«Человек – это живое существо»;

«Все живые существа смертны».

Требуется методом резолюций доказать утверждение «Сократ смертен».

Решение:

Шаг 1. Преобразуем высказывания в дизъюнктивную форму:



Шаг 2. Запишем отрицание целевого выражения (требуемого вывода), т.е. «Сократ бессмертен»:

Шаг 3. Cоставим конъюнкцию всех дизъюнктов (т. е. построим КНФ), включив в нее отрицание целевого выражения:



Шаг 4. В цикле проведем операцию поиска резольвент над каждой парой дизъюнктов:



Получение пустого дизъюнкта означает, что высказывание «Сократ бессмертен» ложно, значит истинно высказывание «Сократ смертен».
Дизъюнктом Хорна называется такой дизъюнкт, у которого k = 0 или k = 1. При k = n = 0 получается пустой дизъюнкт, обозначаемый символом Л.

Фразы Хорна (Horn clause) представляют собой подмножество фраз, содержащих только один позитивный литерал. В общем виде фраза Хорна представляется выражением

р :- q1,...,qn. Такая фраза интерпретируется следующим образом:
"Для всех значений переменных в фразе p истинно, если истинны q1 и ... и qn",

т.е. пара символов ":-" читается как "если", а запятые читаются как "и".





14. Язык Пролог. Решения задач.

Пролог–программа предназначена для решения отдельной задачи. В связи с этим Пролог считается декларативным языком программирования.( построенный: - на описании данных; и - на описании искомого результата).

Пролог может быть использован в различных приложениях, относящихся к искусственному интеллекту :

– общение с ЭВМ на естественном языке;

– символьные вычисления;

– написание компиляторов;

– базы данных;


  • экспертные системы и т. д


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

– константы;

– переменные;

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

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

Переменные служат для обозначения объектов, значения которых меняются в ходе выполнения программы. Имена переменных начинаются с заглавных букв или знака «_». Область действия переменной – предложение. Одноименные переменные в разных предложениях могут иметь разные значения.

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

Функтор различается двумя параметрами (именем и числом параметров):

– point(X, Y, Z) и point(X, Y) – разные предикаты

– point/3 - это означается, что у предиката point 3 аргумента,


– point/2 - это означается, что у предиката point 2 аргумента.

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

1. При записи фактов надо соблюдать следующие правила:
-Имена всех отношений и объектов с маленькой буквы.

-Сначала записывается имя отношения, затем в круглых скобках через запятую объекты.

-В конце ставится точка.

Введем отношение -родитель- (parent) между объектами.

parent (tom, bob).

Это факт, определяющий , что Том является родителем Боба.

Вопрос в обычном прологе начинается с ?-

? - parent (bob, pat).

Yes

?-parent (Y, juli), parent (X, Y).

X=bob

Y=pat

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

child(Y, X) :- parent (X, Y).

eсли условие parent (X, Y). выполняется, то логическим следствием из него будет утверждение child(Y, X).


15. Понятие алгоритма, его свойства, примеры алгоритмически нерешаемых задач.

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

Свойства алгоритмов:


  1. Поочередное выполнение команд алгоритма за конечное число шагов приводит к решению задачи, к достижению цели. Разделение выполнения решения задачи на отдельные операции (выполняемые исполнителем по определенным командам) – важное свойство алгоритмов, называемое дискретностью.
  2. Каждый алгоритм строится в расчете на некоторого исполнителя. Для того чтобы исполнитель мог решить задачу по заданному алгоритму, необходимо, чтобы он  был в состоянии понять и выполнить каждое действие, предписываемое командами алгоритма. Такое свойство алгоритмов называется определенностью (или точностью)алгоритма. (Например, в алгоритме указано, что надо взять 3—4 стакана муки. Какие стаканы, что значит 3—4, какой муки?)


  3. Еще одно важное требование, предъявляемое к алгоритмам, - результативность (или конечность) алгоритма. Оно означает, что исполнение алгоритма должно закончиться за конечное число шагов.

  4. Универсальность. Алгоритм должен быть составлен так, чтобы им мог воспользоваться любой исполнитель для решения анало­гичной задачи. (Например, правила сложения и умножения чисел годятся для любых чисел, а не для каких-то конкретных.)

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

Дискретность (от лат. discretus — разделенный, прерывистый) – это разбиение алгоритма на ряд отдельных законченных действий (шагов).

Детерминированность (от лат. determinate — определенность, точность) - любое действие алгоритма должно быть строго и недвусмысленно опре­делено в каждом случае. 

Конечность - каждое действие в отдельности и алгоритм в целом должны иметь возможность завершения.

Массовость - один и тот же алгоритм можно использовать с разными исходными данными.  Результативность - в алгоритме не было ошибок. 


Существует 4 вида алгоритмов: линейный, циклический, разветвляющийся, вспомогательный. 
Линейный (последовательный) алгоритм — описание действий, которые выполняются однократно в заданном порядке. 
Линейный алгоритм применяется при вычислении арифметического выражения, если в нем используются только действия сложения и вычитания. 

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

Условие — выражение, находящееся между словом «если» и словом «то» и принимающее значение «истина» или «ложь». 
Разветвляющийся алгоритм — алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий. 
Способы задания алгоритма:


  • словесный, (недостаток–многословность, возможна неоднозначность–«он встретил ее на поле с цветами»),

  • табличный (физика, химия и т. д.),

  • графический (блок-схемы).

Примеры алгоритмически нерешаемых задач.

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



следующая страница >>