На головну

лекція 5

  1.  Антонов А. і., Борисов В. а. Лекції по демографії. М., 2011. Лекція 7. С. 373-416.
  2.  Вступна лекція
  3.  Вступна лекція
  4.  Взаємодія неалельних генів (Лекція вчителя)
  5.  Питання 13. За лекцій
  6.  Восьма лекція. Дитячі сновидіння.
  7.  тимчасова селекція

Інформатика, Як було розглянуто вище, вивчає знакові (алфавітні) системи. алгебра - Найбільш адекватний математичний апарат опису дій в них, тому алгебраїчний апарат найкращим чином підходить для опису інформаційних систем загальної природи, абстрактно від їх предметної спрямованості. Інформаційні процеси добре формалізуються за допомогою різних алгебраїчних структур.

алгеброю A називається деяка сукупність певних елементів X, з заданими над ними певними операціяміf (часто визначаються по подібністю з операціями додавання і множення чисел), які задовольняють певним властивостям - аксіом алгебри.

Операція f називається n-місній, Якщо вона пов'язує n операндів (об'єктів - учасників цієї операції).

сукупність операцій алгебри A називається її сигнатурою, а сукупність елементів алгебри - носієм алгебри.

затвердження ( висказивательную форма ) - Основна одиниця, Неподільна з точки зору відображення сенсу інформації (семантики).

висловлювання - Деякий оповідної твердження, про яке можна однозначно сказати ( "відразу подивившись на нього"), істинно воно або помилково. Ці два значення всіляких висловлювань позначаються "Істина" и "Брехня", "true"І" fаlse "або" 1 "і" 0 ".

Мінлива, Значеннями якої можуть бути лише значення "1" або "0", називається логічної змінної або булевої змінної.

Приклад. Розглянемо словосполучення:

1. Москва - столиця США.

2. Житель міста Москва.

3. 5 - 7 + 8.

4. 5 - 9 + 28 = 4.

5. У п'яту тиждень зими було дуже холодно.

6. В Антарктиді живуть тигри.

висловлювання має бути однозначно істинним або однозначно хибним, тому висловлюваннями є тільки затвердження 1), 4), 6).

Приклад. Не є висловлюванням і "парадокс брехуна" (Евбулід, учитель Демосфена, близько 350 років до н. е.): "Те, що я зараз стверджую, - помилково", бо якщо воно істинне - то воно помилкове, а якщо допустити, що воно помилкове, то воно істинне. це невизначена висказивательную форма. Аналогічний приклад належить відомому математику, логіку Геделем (1931 р): "Те, що затверджується в цій пропозиції, не може бути доведено". Якщо його можна спростувати, то його не можна довести, а якщо його не можна спростувати, то його можна довести. Пропозиції такого роду не можуть бути доведені або спростовані в межах тієї мови (тієї теорії, алгебри ), За допомогою якої вони сформульовані. Відомі багато подібних парадокси.

розглядаючи висловлювання, Ми не звертаємо уваги на їх внутрішню структуру і можемо розкладати їх на структурні частини, так само як і об'єднувати їх.

Приклад. Побудуємо з нижче заданих простих висловлювань складові, складні висловлювання, які беруть значення "істина","Брехня":

1. "Зима - холодну пору року".

2. "Пальто - теплий одяг".

3. "Камін - джерело тепла".

Справжнім буде, наприклад, складне вислів: "Зима - холодну пору року і взимку носять пальто", а помилковим буде, наприклад, вислів: "Деякі ходять в пальто, тому на вулиці зима". Придумайте інші приклади.

предикат - висказивательную форма з логічними змінними (безліч значень цих змінних цілком визначено), що має сенс при будь-яких допустимих значеннях цих змінних. Кількість змінних в запису предиката називається йогомісцевістю.

прості висловлювання або предикати не залежить від інших висловлювань або предикатів ( «Не разбіваеми на більш прості"), а складні - залежать хоча б від двох простих.

Приклад. вираз "Х = у" - предикат, "Х> 5" - предикат, А "7> 5" - вислів. Затвердження "Добре" не євисловлюванням, Твердження "Оцінка студента А по інформатики - хороша "- просте вислів, Твердження "Вчора була ясна погода, я був вчора на рибалці" - складне вислів, Що складається з двох простих.

Логічної (булевої) функцією f (х) називається деяка функціональна залежність, в якій аргумент х - логічназмінна із заданим безліччю змін аргументу, а значення функції f (x) беруться з двоелементною безлічі R (f) = {1,0}.

Приклад. задані предикати виду р = "число х ділиться без остачі на 3" і q = "у - день тижня". Знайдемо безліч істинності предикатів р і q, якщо ,  . Отримуємо, що , .

Безліч логічних змінних  з певними над ним операціями: - заперечення або інверсії, - логічного додавання або диз'юнкції, - логічного множення або кон'юнкції називається алгебройпредікатов (і висловлювань ), Якщо ці операції задовольняють наступним аксіом:

1. аксіома подвійного заперечення:

2. аксіоми переместительности операндів (щодо операцій диз'юнкції и кон'юнкції ):

3. аксіоми переместительности операцій диз'юнкції и кон'юнкції (Щодо операндів):

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

5. аксіоми поглинання (множником - множника-суми або складовою - доданка-твори):

6. аксіоми розподілу операції ( диз'юнкції щодо кон'юнкції і навпаки):

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

8. аксіоми нейтральності (взаімноінверсних множників або доданків):

9. аксіома існування одиниці ( істина, True, 1) і нуля ( брехня, False, 0), причому,

З цих аксіом слід ряд корисних співвідношень, наприклад,

три базові операції алгебри предикатів визначаються таблицею їх значень, так як в алгебри предикатів через дискретності значень логічних функцій часто використовується таблична форма завдання функції. Булеву функцію n змінних можна повністю визначити таблицею з 2n рядків.

Отже, ці операції визначаються суміщеної таблицею значень виду

така таблиця всіх значень деякої логічної функції називається таблицею істинності цієї функції.

Приклад. Складемо таблицю істинності функції  . ця таблиця має вигляд

отже, функція тотожно-істинною. Це можна було довести (перевірити) і за допомогою аксіом:

Приклад. Заповнимо таблицю істинності тримісній логічної функції  . ця таблиця має вигляд

Приклад. Зобразимо графічно безліч істинності двомісного предиката виду р (х, у) = "модуль числа х дорівнює модулю числа у", якщо задана область зміни аргументів:  . маємо співвідношення

сенс предикатів р1 (х, у) і р2 (х, у) очевидний. Безліч зображується графіком функції y = | x |, що він дав на рис. 5.1:


Мал. 5.1.Графік функції y = | x |

Крім зазначених трьох базових операцій можна з їх допомогою ввести ще такі важливі операції алгебри предикатів (Можна їх назвати небазових операціями):

1. імплікації: ;

2. еквіваленціі: .

операції імплікації і еквіваленціі, хоча і є часто використовуваними, але не базові, бо вони обумовлені через три введені вище базові операції. Неважко визначити їх таблиці істинності (виконайте це самостійно за допомогою правих частин наведених рівностей).

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

У логічних формулах визначено старшинство операцій, наприклад: дужки, заперечення, кон'юнкція, диз'юнкція (Інші, небазові операції поки не враховуємо).

Завжди істинні формули називають тавтологія.

Логічні функції еквівалентні, якщо збігаються їх таблиці істинності, тобто збігаються області визначення і значення, а також самі значення функції при одних і тих же наборах змінних з числа всіх допустимих значень. Якщо це збіг відбувається на частини безлічі допустимих значень, то формули називаються еквівалентними лише на цій частині (на цьому підмножині).

завдання спрощення логічного виразу складається в перетворенні його до більш простому (по числу змінних, операцій або операндів) еквівалентному висловом. Найбільш простий вид виходить при зведенні функції до постійної - 1 ( істина ) Або 0 ( брехня ).

Приклад. спростимо:

Завдання докази рівності двох логічних виразів (Функцій) полягає у встановленні еквівалентності цих функцій на деякому безлічі значень всіх змінних, що входять в дану функцію.

Приклад. доведемо рівність логічних виразів:  використовуючи аксіоми алгебри предикатів, Отримуємо рівності

Ліва частина рівності приведена до правої частини, тобто дане рівність доведено повністю.

Такі завдання вирішуються за допомогою аксіом алгебри предикатів одним із таких способів:

· Права частина рівності приводиться до лівої частини;

· Ліва частина рівності приводиться до правої частини;

· Обидві частини рівності наводяться до третього висловом.

Логічні функції дозволяють ефективно вирішувати так звані инфологической (інформаційно-логічні) задачі, Доводити твердження.

Інформаційно-логічна (інфологіческая) завдання - Це завдання, в якій необхідно встановити деякі інформаційні або логічні зв'язки і зробити необхідні причинно-наслідкові логічні висновки. Ці завдання виникають в різних областях і часто є погано формалізованими і структурованими. Їх потрібно добре формалізувати і структурувати. Наскільки добре буде можливо це зробити - настільки добре і повно буде вирішена проблема, яка розглядається або завдання. Розглянемо приклад інформаційно-логічної задачі (наприклад, розв'язуваної слідчим, знайомим залгеброю предикатів ).

Приклад. Брауну, Джонсу і Сміту пред'явлено звинувачення в співучасті в пограбуванні банку. В ході слідства Браун сказав, що злочинці були на синьому "Бьюїк", Джонс сказав, що це був чорний "Крайслер", Сміт стверджував, що це був "Форд", але не синій. Кожен вказав неправильно або марку, або колір автомобіля. Визначимо справжній колір і справжню марку автомобіля. Розглянемо прості висловлювання виду: х = "машина - синя", у = "машина - Бьюїк", z = "машина - чорна", u = "машина - Крайслер", v = "машина - Форд". На їх основі вислів Брауна можна записати у вигляді складного логічного виразу виду , вислів Джонса - у вигляді  , а вислів Сміта - у вигляді  Так як в кожному з цих виразів одна з змінних приймає значення "істина", То правдиві та диз'юнкції виду: . за визначенню кон'юнкції,  . це вираз ми взяли через однозначності рівності 1 кон'юнкції і неоднозначності (багатоваріантності) його рівності нулю. спростимо вираз:

Ми використовували той факт, що одночасно не можуть бути істинними два висловлювання щодо кольору або двависловлювання щодо марки машини. Так як кон'юнкція істинна тільки тоді, коли  , То робимо висновок, що автомобіль був чорним "Бьюїком".

закони алгебри висловлювань и предикатів схожі з правилами, по яким людина робить умовиводи, Доводить, мислить.

Приклад. операції кон'юнкції, диз'юнкції, заперечення алгебри висловлювань - Аналоги спілок "і", "або", приставки «не», використовуваних (можливо, інтуїтивно) при вираженні думки людиною.

Щоб перекласти на ЕОМ роботи розумового характеру, ці правила необхідно строго сформулювати, формалізувати. Це дозволяє здійснити алгебра логіки. Наведемо деякі аксіоми логіки - науки, що вивчає методи докази і спростування тверджень.

1. аксіома виключення третього: або має місце вислів, Або його заперечення.

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

3. аксіома подвійного заперечення: дворазове заперечення будь-якого затвердження рівносильно вихідного твердженням.

4. аксіома тотожності: всяке вислів тотожне самому собі.

якщо висловлювання x і y пов'язані один з одним відношенням  , То кажуть, що вислів y випливає звисловлювання x (або y - наслідок x); якщо безліч істинності Х висловлювання х містить безліч істинності Yвисловлювання y, то вислів x - умова, вислів y - висновок, а саме співвідношення - висновок.

Доведення формальних математичних тверджень (теорем) - послідовність коректних висновків, що ведуть від умови до висновку. алгебра логіки допомагає доводити теореми (дає загальні підходи і методи доведення).

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




 лекція 2 |  Лекція 2: Інформація, її уявлення і вимір |  лекція 3 |  лекція 7 |

© um.co.ua - учбові матеріали та реферати