|
х
|
у
|
x↓y
|
x←y
|
x→y
|
x⊕y
|
x|y
|
x
& y
|
x
≡ y
|
x
∨ y
|
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
0
|
1
|
0
|
|
0
|
1
|
0
|
0
|
1
|
1
|
1
|
0
|
0
|
1
|
|
1
|
0
|
0
|
1
|
0
|
1
|
1
|
0
|
0
|
1
|
|
1
|
1
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
1
|
Дизъюнктивная
нормальная форма (ДНФ)
Простой конъюнкцией или конъюнктом называется
конъюнкция некоторого конечного набора переменных или их отрицаний, причём
каждая переменная встречается не более одного раза. Дизъюнктивной нормальной
формой или ДНФ называется дизъюнкция простых конъюнкций. Элементарная
конъюнкция:
· правильная, если в неё каждая
переменная входит не более одного раза (включая отрицание);
· полная, если в неё каждая переменная
(или её отрицание) входит ровно 1 раз;
· монотонная, если она не содержит
отрицаний переменных.
Например 
-
является ДНФ.
Теорема
(о СДНФ)
Всякая тождественно не равная 0
функция f(
, 
,…,
) допускает представление f(, ,…,
) = ∨f(
,…,
))x
…x
(1) ,
где дизъюнкция берется по всем
наборам C=(,…,) из 0 и 1, для которых f(c)
= 1
Доказательство: Пусть
функция f(, ,…,)≠0. По лемме о
разложении функции по компонентам при k=n получаем:
f(, ,…,) = ∨f(,…,))x…x правой части этого равенства
выбросим все нулевые дизъюнктивные слагаемые, для которых f(,…,) =0, останутся слагаемые, в
которых f(,…,)=1. Равенство принимает вид:
f(, ,…,) = ∨f()= 1x…x
Определение: Правая
часть представления (1) называется СДНФ функции f.
Замечание: Каждое
слагаемое в СДНФ называется конституентой единицы. Конституента единицы x…x=1 на единственном наборе , =,, , =
,, , =.
Замечание: Всякая
функция допускает представление в виде СДНФ, которая построена из функций
множества F={&, ∨, ¬} (2).
Следовательно, множество F составляет полную систему. Система F3={x/y},
состоящая из единственной функции (штрих Шеффера), составляет полную систему
Замечание: Для всякой
не равной тождественно нулю функции существует единственная СДНФ.
Легко убедиться, что каждой булевой
функции соответствует некоторая ДНФ, а функции отличной от тождественного нуля
- даже СДНФ. Для этого достаточно в таблице истинности этой функции найти все
булевы векторы, на которых её значение равно 1, и для каждого такого вектора 
построить
конъюнкцию 
, где 
.
Дизъюнкция этих конъюнкций является СДНФ исходной функции, поскольку на всех
булевых векторах её значения совпадают со значениями исходной функции.
Например, для импликации 
результатом
является 
, что можно
упростить до 
.
Конъюнктивная
нормальная форма (КНФ)
Конъюнктивная нормальная форма1 (КНФ)
определяется двойственно к ДНФ. Простой дизъюнкцией или дизъюнктом называется
дизъюнкция одной или нескольких переменных или их отрицаний, причём каждая
переменная входит в неё не более одного раза. КНФ - это конъюнкция простых
дизъюнкций.
Теорема
(о СКНФ):
Всякая не равная тождественно 1 функция
f(, ,…,) допускает представление
f(, ,…,) = & f(
, 
,…,
) x¬
∨…∨x¬
) (3),
где конъюнкция берется по всем
наборам C = (, ,…,) из 0 и 1, для которых f(C)
= 0.
Доказательство: заметим,
что ¬(xc) = x¬c. Пусть функция f(, ,…,) ≠1. Тогда ¬f≠0
и потому функция ¬f допускает представление в виде СДНФ.
¬ f(, ,…,) =∨¬f(C)=1 x…x
Берем отрицание от обеих частей.
f(, ,…,) =
¬∨f(C)=0(x…x) = &f(C)=0¬( x…x) = &f(C)=0(¬x…¬x) = &f(C)=0(x¬…x¬)
Определение: Правая часть
представления (3) называется СКНФ для функции f.
Замечание: для всякой
функции f≠1 СКНФ единственна.
Совершенной конъюнктивной нормальной
формой (СКНФ),
относительно некоторого заданного конечного набора переменных, называется такая
КНФ, у которой в каждую дизъюнкцию входят все переменные данного набора, причём
в одном и том же порядке. Поскольку (С)КНФ и (С)ДНФ взаимодвойственны, свойства
(С)КНФ повторяют все свойства (С)ДНФ, грубо говоря, «с точностью до наоборот».
КНФ может быть преобразована к эквивалентной
ей ДНФ путём раскрытия скобок по правилу:
которое выражает дистрибутивность
конъюнкции относительно дизъюнкции. После этого необходимо в каждой конъюнкции
удалить повторяющиеся переменные или их отрицания, а также выбросить из
дизъюнкции все конъюнкции, в которых встречается переменная вместе со своим
отрицанием. При этом результатом не обязательно будет СДНФ, даже если исходная
КНФ была СКНФ. Точно также можно всегда перейти от ДНФ к КНФ. Для этого следует
использовать правило
выражающее дистрибутивность
дизъюнкции относительно конъюнкции. Результат нужно преобразовать описанным
выше способом, заменив слово «конъюнкция» на «дизъюнкция» и наоборот.
Правила
и стратегия игры в шашки
Пространственно - композиционная игра шашки
напоминает игру типа «крестиков-ноликов». Квадратура развивает пространственное
мышление и «видение поля» - умение взглядом охватить и оценить ситуацию на
поле, заполненном шашками игроков, вычислить тенденцию к возможностям
построения квадратов и шашек своих и противника и определить оптимальную
стратегию.
Поочередно делая ходы на доске 8×8
или
меньшего размера, игроки устанавливают свои шашки таким образом, чтобы они не
составили четыре угла квадрата в любом из мыслимых направлений на доске. При
этом, стараясь избежать построения квадрата своими шашками, игрок старается
заставить противника поставить свою шашку так, чтобы в совокупности с тремя
другими его шашками они составили бы квадрат. Первый появившийся и замеченный игроками
квадрат определяет проигравшего - автора этой фигуры.
Игра может вестись не на всей доске, а на ее
части. Для полей 4×4, 6×6 и
8×8
возможно
соответственно построение 20, 105 и 336 квадратов разного размера и
расположения. Несмотря на большое количество возможных вариантов построения
квадратов и, соответственно, трудность предусмотреть и предвидеть возможные
тактические ходы, существует беспроигрышная стратегия при игре на полях 6×6
и
8×8
для
черных.
Начинающий вторым игрок дублирует ходы белых
относительно одной из двух осей симметрии игрового поля либо относительно
центра доски. Асимметричная стратегия: на ход x1
следует ход y7 или y8.
Раз выбранная ось симметрии выдерживается всю игру. Центросимметричная
стратегия: на ход x1 следует
ход y8 и т. д. Игра при
такой стратегии становится монотонной и неинтересной, и применять ее следует
разве что при необходимости обязательного выигрыша. На полях 5×5
и
7×7
эта
стратегия не применима ввиду отсутствия графических осей и центра симметрии.
По договоренности игру можно вести до полного
закрытия поля шашками. Итоговым результатом будет разность квадратов, при их
равенстве будет ничья.
Математическая
модель цифрового устройства для игры в шашки
Разработаем математическую модель для игры в
шашки, будем использовать для этого игровое поле 4*4. Обозначим наши переменные
следующим образом:
Пусть 
- переменная для белых шашек, где x =
1,2,3,4,5,6,7,8.
Тогда 
- переменная для черных шашек, где
у = 1,2,3,4,5,6,7,8.
Из этого следует что:
= 0 - если клетка игрового поля пуста,
= 1- если на клетке стоит белая
шашка,
= 0 - если клетка игрового поля
пуста,
= 1- если на клетке стоит черная
шашка.
Ниже представлен рисунок нашей
игровой доски.
Посмотрев на рисунок можно отметить
что х1=1 и х2=1 так как только на них расположены белые шашки, остальные
значения х=0, тоже можно и заметить и с у7 и у8 которые соответственно тоже
равны единице а все остальные нулю.
Теперь рассмотрим три
последовательные развития игры представленные чуть ниже в виде таблицы. Это
выигрыш белых фигур соответственно проигрыш черных, выигрыш черных или проигрыш
белых, и ничья когда ни одна из сторон не победит но и не проиграет.
Таблица№1
Выигрыш черных шашек.
|
№
|
Текущий
ход
|
Следующий
ход
|
|
x
|
y
|
|
|
|
1
|
11000000
|
00000011
|
10010000
|
00000011
|
|
2
|
10010000
|
00000011
|
10010000
|
00000110
|
|
3
|
10010000
|
00000110
|
00110000
|
00000110
|
|
4
|
00110000
|
00000110
|
00010000
|
10000010
|
|
5
|
10000010
|
00000100
|
10000010
|
|
6
|
00000100
|
10000010
|
00000000
|
10010000
|
математический модель игра булевая
функция
Таблица№2
Исход игры: ничья.
|
№
|
Текущий
ход
|
Следующий
ход
|
|
x
|
y
|
|
|
|
1
|
11000000
|
00000011
|
01100000
|
00000011
|
|
2
|
01100000
|
00000011
|
01100000
|
00000101
|
|
3
|
01100000
|
00000101
|
01001000
|
00000101
|
|
4
|
01001000
|
00000101
|
01001000
|
00100001
|
|
5
|
01001000
|
00100001
|
01000010
|
00100001
|
|
6
|
01000010
|
00100001
|
01000010
|
10000001
|
|
7
|
01000010
|
10000001
|
00010010
|
10000001
|
|
8
|
00010010
|
10000001
|
00010010
|
10000100
|
|
9
|
00010010
|
10000100
|
00011000
|
10000100
|
|
10
|
00011000
|
10000100
|
00011000
|
10100000
|
|
11
|
00011000
|
10100000
|
10000000
|
|
12
|
01010000
|
10000000
|
01010000
|
00000001
|
|
13
|
01010000
|
10000000
|
01000100
|
00000001
|
|
14
|
01000100
|
10000000
|
01000000
|
10000000
|
Таблица№3
Выигрыш белых шашек.
|
№
|
Текущий
ход
|
Следующий
ход
|
|
x
|
y
|
|
|
|
1
|
11000000
|
00000011
|
01100000
|
00000011
|
|
2
|
01100000
|
00000011
|
01100000
|
00000110
|
|
3
|
01100000
|
00000110
|
01000001
|
00000010
|
|
4
|
01000001
|
00000010
|
01000001
|
00001000
|
|
5
|
01000001
|
00001000
|
00010001
|
00001000
|
|
6
|
00010001
|
00001000
|
00010001
|
00100000
|
|
7
|
00010001
|
00100000
|
10010000
|
00000000
|
Заключение
В заключении своей курсовой работы хотелось бы
отметить тот факт что игровые модели могут иметь отношение не только к детским
играм (в том числе и компьютерным), но и к вещам весьма серьезным.
Например, полководец перед сражением в условиях
наличия неполной информации о противостоящей армии должен разработать план : в
каком порядке вводить в бой те или иные части и т.д., учитывая и возможную
реакцию противника. Есть специальный достаточно сложный раздел современной
математики - теория игр, - изучающий методы принятия решений в условиях
неполной информации.
Поэтому я считаю что в настоящее время
прикладная математика и ЭВМ являются одним из определяющих факторов
научно-технического прогресса. Они способствуют ускорению развития ведущих
отраслей народного хозяйства, открывают принципиально новые возможности
моделирования и проектирования сложных систем с выбором оптимальных параметров
технологических процессов.
Список
использованной литературы
1. Гаврилов
Г.П., Сапоженко А.А. Сборник задач по дискретной математике. - М.: Наука, 2009.
. Кузнецов
О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. - М.:
«Энергия», 2002. - 344 с.
. Марченков
С.С. Замкнутые классы булевых функций. - М.: Физматлит, 2000.
. Яблонский
С.В. Введение в дискретную математику. - М.: Наука, 2006.
. Алексеев
В.Б. Дискретная математика (курс лекций, II семестр). Сост. А.Д. Поспелов
. Быкова
С.В., Буркатовская Ю.Б., Булевы функции, учебно-методический комплекс, Томск,
2006
. Учебные
пособия кафедры математической кибернетики ВМиК МГУ.
Приложение
Программа
для игры “шашки” на языке С++ Builder
=====НАЧИНАЕМ
ХОД======
{Point; (WhoseTurn
== Black) // =====ПРОВЕРЯЕМ, ДЕЙСТВИТЕЛЬНО ЛИ ХОДИТ ЧЕЛОВЕК=====
return;
(HWindow); (&Point); (HWindow, &Point); = bd->GetValidSquare(Point,
WhoseTurn); (MoveStartPoint. x)
{
= bd->GetPieceType(MoveStartPoint); hDC = GetDC(HWindow); >ClearSquare(hDC,
MoveStartPoint); = TRUE; (HWindow, hDC);
}
}
Функция
WMLButtonUp(): TCheckersWindow:: WMLButtonUp(TMessage&)
{Point;
(); (! HoldingPiece || WhoseTurn == Black) ; (&Point); (HWindow,
&Point); = bd->GetEmptySquare(Point); hDC = GetDC(HWindow); (MoveEndPoint.
x && bd->UserMove(MoveStartPoint, MoveEndPoint))
{ // ====ЕСЛИ
ЧЕЛОВЕК МОЖЕТ СЮДА ПОСТАВИТЬ ФИШКУ... =====>RedrawBoard(hDC); // =========ТО
ПЕРЕРИСОВЫВАЕМ ДОСКУ=======
EnableMenuItem(hMenu,
CM_UNDO, MF_BYCOMMAND | MF_ENABLED); (hMenu, CM_REDO, MF_BYCOMMAND |
MF_DISABLED | MF_GRAYED);
if (!
bd->AnotherJump()) // =====МОЖНО СДЕЛАТЬ ПОВТОРНЫЙ ХОД? ========
{(bd->NoMoreBlack())
// ====ЕСЛИ БОЛЬШЕ НЕОСТАЛОСЬ ФИШЕК КОМПЬЮТЕРА... . ===
{(GetApplication()
- >ExecDialog(new TEndDialog(this, "UserWonDlg")) // ТО
ЧЕЛОВЕК
ВЫИГРАЛ!
==
IDYES)
{(HWindow,
WM_COMMAND, CM_FILENEW, 0L); (HWindow, hDC); ;
}
{(HWindow,
WM_COMMAND, CM_EXIT, 0L); (HWindow, hDC); ;
}
}(HWindow,
WM_COMMAND, CM_MOVE, 0L); // ==ПЕРЕКЛЮЧАЕМСЯ
НА
ХОД===
} //
=======КОМПЬЮТЕРА=======// НЕЯВНЫЙ ВЫЗОВ ФУНКЦИИ
; //
ComputersMove()
}
{>DrawPiece(hDC,
MovingPieceType, MoveStartPoint);
}=
FALSE; (HWindow, hDC);
}
Функция
ComputersMove(): TCheckersWindow:: ComputersMove(RTMessage)
{>EndUsersTime();
= Black; (hMenu, 0, MF_BYPOSITION | MF_DISABLED | MF_GRAYED); (hMenu, 1,
MF_BYPOSITION | MF_DISABLED | MF_GRAYED); (hMenu, 3, MF_BYPOSITION |
MF_DISABLED | MF_GRAYED); (hMenu, CM_MOVE, MF_BYCOMMAND | MF_ENABLED |_STRING,
CM_STOP, "&Stop"); (HWindow); >ComputersTurn(); // =======ПЕРЕКЛЮЧАЕМСЯ
НА
РАБОТУ
ИИ========hDC
= GetDC(HWindow); >RedrawBoard(hDC); (HWindow, hDC); = Red; CursorPoint;
(&CursorPoint); (HWindow, &CursorPoint);
#pragma
warn - stv(PtInRect(&MainWndRect, CursorPoint))
/*SetCursor(CursorHand)
*/;
#pragma
warn +stv(hMenu, CM_STOP, MF_BYCOMMAND | MF_ENABLED |_STRING, CM_MOVE,
"move you"); (hMenu, 0, MF_BYPOSITION | MF_ENABLED); (hMenu, 1,
MF_BYPOSITION | MF_ENABLED); (hMenu, 3, MF_BYPOSITION | MF_ENABLED); (HWindow);
(bd->NoMoreRed()) // ====ЕСЛИ
БОЛЬШЕ
НЕОСТАЛОСЬ
ФИШЕК
ЧЕЛОВЕКА...
. ===
{(GetApplication()
- >ExecDialog(new TEndDialog(this, "GameWonDlg")) // ===ТО
КОМПЬЮТЕР===
==
IDYES) // ======ВЫИГРАЛ======
{(HWindow,
WM_COMMAND, CM_FILENEW, 0L); ;
}
{(HWindow,
WM_COMMAND, CM_EXIT, 0L); ;
}
}>StartUsersTime();
// ======ХОД
ЧЕЛОВЕКА========
}