Семантика

Лекция № 10

(лек. 2 час + прак. занят 10 час + лаб. 2 час. + самос. 4 час)

АЛГЕБРА ЛОГИКИ

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

Булева алгебра логики

Булева алгебра - частный случай алгебры логики.

f: Bⁿ → B, B={0,1};

Ъ: B^2® B, Щ: B^2® B, щ: B® B

A=‹M,W ›, M№ Ж, W ={f_jⁱ}, i,jО N f_jⁱ: M^j® M.

A=‹B_(u), И, З,` ›

A=‹B_(U),Ъ, Щ, щ ›

Алгебра логики - множество высказываний и операций - одной унарной и 4 бинарных:

А₁ = ‹b, {Ї, , , →, ~}›

Ї: {0,1} → {0,1} - отрицание

: {0,1}² → {0,1} - конъюнкция (лог. умножение) – " и "

: {0,1}² → {0,1}- дизъюнкция (лог. сложение) - " или "

Язык алгебры логики.

a ₁ ={a: A^* ; AЅ ^G2ѕ 2}

A= { x, y, z…x₁ , y_1, z₁ ,…..,……,Ъ, Щ, щ, (,) }

G₂=‹T=A, H, J, P› -правило синтаксиса (Т- терминальные символы, Н- нетерминальные)

Среди порождающих процедур используют разного рода грамматики:

a О А^* = А И А² И ….И Аⁿ

А^* - итерация – объединение символов алфавита

Синтаксис

R = S И S _{2 И} P₂

семантика

P = {J(JЪ J), J® (JЪ J), J® (щ J), J® S, J® x(y, z,..)}

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

либо реле различного способа действия

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

(упрощение, минимизация) с целью алгоритмизации решения задач.

В алгебре логики высказывания рассматриваются только с точки зрения истинности или ложности без рассматривания их смысла.

Примеры (задачи для самостоятельного решения):

1. Задача Венна.

В уставе клуба записано:

o финансовый комитет избирается из состава членов общего комитета

o никто не может быть одновременно членом и общего, и библиотечного комитета, если только он не состоит также и членом финансового комитета.

o никто из членов библиотечного комитета не может быть в финансовом комитете.

Упростить правила устава (до 2-х правил).

B, g, f - библиотечный, общий и финансовый комитеты.

→ - "если, то"

Учтем, что x → y = не x y

Интерпретация выражения эквивалентна следующему:

§ члены финансово комитета избираются из членов общего

§ члены общего комитета не могут быть членами библиотечного

o Выяснить, кто из детей разбил окно, если каждый из них сделал следующие заявления:

Ваня:

§ Я не виноват

§ Я не подходил к окну

§ Михаил знает, кто разбил окно

Павел:

§ Я не разбивал окно

§ Константин врет

§ Это сделал Михаил

Константин:

§ Окно разбил не я

§ С Михаилом я не дружу

§ Это сделал Павел

Михаил:

§ Моей вины здесь нет

§ Стекло разбил Виктор

§ За меня может поручиться Константин: мы с ним друзья

В дальнейшем Ваня, Павел, Костя и Миша признались, что одно из 3-х их заявлений является неверным (показание истинно, только если два заявления истинны, а одно ложно).

Решение

Замечание

1. Для построения логической теории используются формализованные языки (непустое множества алфавита, синтаксиса и семантики), которые являются средством познания мира и средством выражения мысли.

α = ‹ A, S₁, S₂› (A - символы алфавита, S₁ - синтаксис, S₂ - семантика).

2. В рамках формализированных языков строятся логические теории, с помощью которых решаются логические задачи.

3. Во множестве формул языка выделяют класс формул - аксиомы (логич. закон, базис). Например, выражение x не x = 1