Логическое программирование

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

В рамках подготовки к ЕГЭ по информатике эта парадигма имеет прикладное значение: учащимся необходимо уметь формализовывать логические задачи, работать с таблицами истинности, строить логические схемы, определять эквивалентность формул, а также использовать аппарат логики для решения задач на поиск, перебор и доказательство.

Теоретические основы логического программирования 

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

2. Основные элементы логического программирования

3. Факты – утверждения о мире, которые принимаются как истинные.

4. родитель(иван, анна).

5. родитель(мария, анна).

6. Правила – логические зависимости, выводящие новые знания из фактов.

7. мать(X, Y) :- родитель(X, Y), женщина(X).

8. Запросы – формулировки задачи, которые система должна проверить или доказать.

9. ?- мать(мария, анна).

10. Переменные – используются для обобщения правил и вывода. 

Логический вывод

Вычисление в логическом программировании основывается на правилах резолюции и унификации.

• Унификация – процесс сопоставления выражений для поиска замены переменных.

• Резолюция – правило вывода, позволяющее строить доказательство цели, комбинируя факты и правила. 

Связь с математической логикой

Формулы можно записывать в форме:

A ∧ B → C

или эквивалентно через клаузы Хорна, используемые в системах логического программирования (например, Prolog).

Правила корректного использования логического программирования

1. Ясность фактов и правил: каждый факт должен представлять однозначное утверждение, правила не должны противоречить друг другу.

2. Минимизация избыточности: не следует дублировать факты, лучше формализовать их в обобщённом виде.

3. Правильное использование переменных: переменные должны быть универсальными (X, Y, Z), а конкретные объекты – атомами (например, иван, анна).

4. Избегание бесконечных рекурсий: рекурсивные правила должны иметь условие завершения.

5. Оптимизация порядка фактов и правил: более простые условия лучше размещать в начале.

Практическая значимость для ЕГЭ

В заданиях ЕГЭ по информатике учащиеся встречают:

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

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

Упражнения

Упражнение 1. Таблица истинности

Составьте таблицу истинности для выражения:  (A → B) ∧ (¬C ∨ A)

а) Определите число наборов переменных (A, B, C), при которых выражение истинно.
б) Найдите эквивалентное выражение с использованием только операций «И», «ИЛИ», «НЕ».

Упражнение 2. Построение правил

Запишите на языке логического программирования правило «X является братом Y, если у них общий родитель и X – мужчина»: 
брат(X, Y) :- родитель(Z, X), родитель(Z, Y), мужчина(X), X \= Y.

а) Объясните роль условия X \= Y.
б) Составьте запрос, позволяющий найти всех братьев Анны.

Упражнение 3. Законы логики

Докажите, что выражение  ¬(A ∨ B) ↔ (¬A ∧ ¬B)  эквивалентно закону де Моргана.

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

Упражнение 4. Логическая задача ЕГЭ

Условие: «Если число делится на 6, то оно делится на 2 и на 3».
а) Запишите утверждение в виде формулы:

(n mod 6 = 0) → ((n mod 2 = 0) ∧ (n mod 3 = 0))

б) Составьте таблицу истинности для делимости на 2 и 3.
в) Объясните, почему данное утверждение всегда истинно.

Упражнение 5. Рекурсивные правила

Опишите правило, определяющее, является ли X предком Y: 
предок(X, Y) :- родитель(X, Y).
предок(X, Y) :- родитель(X, Z), предок(Z, Y).

а) Объясните, как работает рекурсия в данном правиле.
б) Составьте запрос для поиска всех предков конкретного человека.
в) Укажите, что произойдёт, если убрать базовое правило.

Заключение

Логическое программирование – это мощная парадигма, основанная на описании фактов и правил, а не последовательности действий. Она тесно связана с математической логикой и имеет важное значение в подготовке к ЕГЭ по информатике, особенно в заданиях на таблицы истинности, преобразование выражений, построение схем и анализ логических зависимостей.

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