litceysel.ru 1

Министерство образования российской федерации


Московский государственный институт электроники и математики

(технический университет)

Кафедра ИКТ


ОТЧЕТ ПО КУРСОВОЙ РАБОТЕ ПО ДИСЦИПЛИНЕ «ИНФОРМАТИКА»

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


Москва 2011 год



Оглавление


Оглавление 2

Теоретическая часть. 3

Логические переменные и логические операции. 3

Логические функции и таблицы истинности. 4

Задача: 5

Практическая часть. 5

Таблица для переменных. 5

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

Чтение строки. 6

Установка. 6

Литература. 7

Приложение(код). 8



Теоретическая часть.

Логические переменные и логические операции.


Простые высказывания в алгебре логики обозначаются заглавными латинскими буквами: А, В, С, D,… и т. д. Составные высказывания на естественном языке образуются с помощью союзов. В алгебре логики эти союзы заменяются логическими операциями. В соответствии с алгеброй логики любое составное высказывание можно рассматривать как логическую функцию F(А, В, С, …), аргументами которой являются логические переменные А, В, С… (простые высказывания). Логические функции и логические переменные (аргументы) принимают только два значения: «истина», которая обозначается логической единицей – 1 и «ложь», обозначаемая логическим нулем – 0. Логическую функцию называют также предикатом.

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


  • Логическая операция ИНВЕРСИЯ (отрицание). В естественных языках соответствует словам неверно, ложь или частице “не”, в языках программирования обозначается “not”.

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

Математическая запись данной операции для логической переменной А будет иметь вид:

  • Логическая операция КОНЪЮНКЦИЯ (логическое умножение). В естественных языках соответствует союзу “и”, в языках программирования обозначается “and”.

Конъюнкция каждым простым высказываниям ставит в соответствие составное высказывание, являющееся только тогда истинным, когда являются истинными простые высказывания, образующие составное высказывание.

Математическая запись данной операции для логических переменных A, В, С, … будет иметь вид:

F = A and B and C and …

  • Логическая операция ДИЗЪЮНКЦИЯ (логическое сложение). В естественных языках соответствует союзу или, в языках программирования обозначается “or”.

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

Математическая запись данной операции для логических переменных A, В, С, … будет иметь вид:

F = A or B or C…

Существуют и другие, но их можно вывести с помощью первых трёх.

Логические функции и таблицы истинности.

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


Например, для логической функции F = A v B v C (дизъюнкции) трех логических переменных А, В, и С таблица истинности будет иметь вид, показанный на рис. Для записи значений логических переменных и логической функции данная таблица истинности содержит 8 строк и 4 столбца, т. е. число строк для записи значений аргументов и функции любой таблицы истинности будет равно 2n, где n – число аргументов логической функции, а число столбцов равно n + 1.

Таблица 1


Задача:


Написать программу, получающую на входе функцию и строящую для неё таблицу.

Практическая часть.

Таблица для переменных.


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

  • A = [0, 0, 0, 0, 1, 1, 1, 1]

  • B = [0, 0, 1, 1, 0, 0, 1, 1]

  • C = [0, 1, 0, 1, 0, 1, 0, 1]

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

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


Поскольку у нас таблица состоит из списков, при логических операциях над переменными нам надо выполнять логическую операцию между двумя соответствующими элементами двух списков(за исключением отрицания). Пример: F(A and B) =

  • A = [0, 0, 1, 1]

  • B = [0, 1, 0, 1]

  • F = [A[1] and B[1], [A[2] and B[2], [A[3] and B[3], [A[4] and B[4]] =>

  • F = [0, 0, 0, 1]

Чтение строки.


Самой сложной по реализации оказалась эта часть, так как в большей степени требует знания программирования, чем понимания логических функций. Вводить в программу надо содержимое логической функции, то есть для функции F(A and B) мы введём в программу: A and B. Программа посчитает кол-во переменных, составит таблицу истинности для них (повторяющиеся переменные в таблицу не войдут), произведёт логическую операцию и выдаст ответ в виде:

  • A = [0, 0, 1, 1]

  • B = [0, 1, 0, 1]

  • F = [0, 0, 0, 1]

Установка.


  • На windows или linux должен стоять Python версии 2.7.

  • Для запуска программы откройте исполняемый файл log_fun2.py

Литература.


  1. Лекции

  2. http://fictionbook.ru/author/vladimir_nikolaevich_yashin/informatika_apparatniye_sredstva_persona/read_online.html?page=5

Приложение(код).

# Napisat' programmu, poluchajuwuju na vhode logicheskuju funkciju i strojawuju dlja nee tablicu istinnosti.

import math


##def narnie(n):

## x = 2**(2**n)

## return x

##

##print "kolvo n-arnih funkchiy dlya 2 =", narnie(0)


#n = int(raw_input('vvedite chislo peremennih'))

fstr = raw_input('vvedite f-ciu')

flist = fstr.split(' ')

new_list = []


##func = flist[1]

n = 0


def log_and(a,b):

f =[]

qaz = 0

while qaz < len(a):

if a[qaz] == 1 and b[qaz] == 1:

f.append(1)

elif a[qaz] == 0 or b[qaz] == 0:

f.append(0)

qaz += 1

return f


def log_or(a,b):

f = []

qaz = 0

while qaz < len(a):

if a[qaz] == 1 or b[qaz] == 1:

f.append(1)

elif a[qaz] == 0 and b[qaz] == 0:

f.append(0)

qaz += 1

return f


def log_not(a):

f = []

qaz = 0

while qaz < len(a):

if a[qaz] == 1:

f.append(0)

elif a[qaz] == 0:

f.append(1)


qaz += 1


return f


ii = 0


while ii < len(flist):

if flist[ii] == "A" or flist[ii] == "B" or flist[ii] == "C" or flist[ii] == "D" or flist[ii] == "E":

n += 1

new_list.append(flist[ii])

if new_list.count(flist[ii]) > 1:

n -=1

if flist[ii] == "and":

new_list.append(flist[ii])

ii+=1


stroki = 2 ** n

stolbchi = n+1


e = []

for x in range(stolbchi):

e.append(2**x)


for qwe in range(0,n+1):


asd = []


while len(asd) < stroki:

for x in range(0, stroki/e[qwe]):

asd.append(0)

for x in range(stroki/e[qwe],stroki/e[qwe-1]):

asd.append(1)


if qwe == 1:

A = asd

print A

pl = [A]


elif qwe == 2:

B = asd

print B

pl = [A,B]

elif qwe == 3:

C = asd

print C

pl = [A,B,C]

elif qwe == 4:

D = asd

print D

pl = [A,B,C,D]

elif qwe == 5:

E = asd

print E

pl = [A,B,C,D,E]

iii = 0


new_list = []

for t in flist:

new_list.append(t)


s =0

while iii < len(flist):

if iii == 0: pass

if new_list[iii] == "A" or new_list[iii] == "B" or new_list[iii] == "C" or new_list[iii] == "D" or new_list[iii] == "E":

new_list[iii] = pl[s]

if new_list.count(flist[iii]) < 1:

s += 1

else:

while new_list.count(flist[iii]) > 0:

new_list[new_list.index(flist[iii])] = new_list[iii]


iii+=1


iii = 0

while iii < len(new_list):

if new_list[iii] == "not":

while new_list.count("not") > 0:

new_list[iii+1] = log_not(new_list[iii+1])

new_list.pop(iii)


iii += 1


iii = 0

while iii < len(new_list):


if new_list[iii] == "and":

while new_list.count("and") > 0:

new_list[iii] = log_and(new_list[iii-1],new_list[iii+1])

new_list.pop(iii-1)

new_list.pop(iii)


iii+=1


iii = 0

while iii < len(new_list):

if new_list[iii] == "or":

while new_list.count("or") > 0:

new_list[iii] = log_or(new_list[iii-1],new_list[iii+1])

new_list.pop(iii-1)

new_list.pop(iii)


iii += 1


## for m in new_list:

## if m == flist[iii]:

## new_list[new_list.index(flist[iii])] = new_list[iii]


print "F =", new_list


##if flist[iii] == "and":

## c = log_and(a,b)


##

##

##if func == 'and':

## c = log_and(a,b)

##elif func == 'or':

## c = log_and(a,b)

##elif func == 'xor':

## pass

##else:

## print u'