![]() |
|
![]() |
|
|
Thread Tools | Display Modes |
|
|
#1 |
|
Programming Guru
![]() |
I'd like to convert the following truth table in to a logical expression:
INPUT OUTPUT [0, 0, 0, 0, 0, 0, 0] [1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0] [0, 0, 0, 0, 0, 0, 1] [1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0] [0, 0, 0, 0, 0, 1, 0] [1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1] [0, 0, 0, 0, 0, 1, 1] [1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1] [0, 0, 0, 0, 1, 0, 0] [1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1] [0, 0, 0, 0, 1, 0, 1] [1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1] [0, 0, 0, 0, 1, 1, 0] [1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1] [0, 0, 0, 0, 1, 1, 1] [1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0] [0, 0, 0, 1, 0, 0, 0] [1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1] [0, 0, 0, 1, 0, 0, 1] [1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1] [0, 0, 0, 1, 0, 1, 0] [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0] [0, 0, 0, 1, 0, 1, 1] [0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0] [0, 0, 0, 1, 1, 0, 0] [0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1] [0, 0, 0, 1, 1, 0, 1] [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1] [0, 0, 0, 1, 1, 1, 0] [0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1] [0, 0, 0, 1, 1, 1, 1] [0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1] [0, 0, 1, 0, 0, 0, 0] [0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1] [0, 0, 1, 0, 0, 0, 1] [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0] [0, 0, 1, 0, 0, 1, 0] [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1] [0, 0, 1, 0, 0, 1, 1] [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1] [0, 0, 1, 0, 1, 0, 0] [1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0] [0, 0, 1, 0, 1, 0, 1] [1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0] [0, 0, 1, 0, 1, 1, 0] [1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1] [0, 0, 1, 0, 1, 1, 1] [1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1] [0, 0, 1, 1, 0, 0, 0] [1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1] [0, 0, 1, 1, 0, 0, 1] [1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1] [0, 0, 1, 1, 0, 1, 0] [1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1] [0, 0, 1, 1, 0, 1, 1] [1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0] [0, 0, 1, 1, 1, 0, 0] [1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1] [0, 0, 1, 1, 1, 0, 1] [1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1] [0, 0, 1, 1, 1, 1, 0] [1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0] [0, 0, 1, 1, 1, 1, 1] [1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0] [0, 1, 0, 0, 0, 0, 0] [1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1] [0, 1, 0, 0, 0, 0, 1] [1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1] [0, 1, 0, 0, 0, 1, 0] [1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1] [0, 1, 0, 0, 0, 1, 1] [1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1] [0, 1, 0, 0, 1, 0, 0] [1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1] [0, 1, 0, 0, 1, 0, 1] [1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0] [0, 1, 0, 0, 1, 1, 0] [1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1] [0, 1, 0, 0, 1, 1, 1] [1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1] [0, 1, 0, 1, 0, 0, 0] [0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0] [0, 1, 0, 1, 0, 0, 1] [0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0] [0, 1, 0, 1, 0, 1, 0] [0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1] [0, 1, 0, 1, 0, 1, 1] [0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1] [0, 1, 0, 1, 1, 0, 0] [0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1] [0, 1, 0, 1, 1, 0, 1] [0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1] [0, 1, 0, 1, 1, 1, 0] [0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1] [0, 1, 0, 1, 1, 1, 1] [0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0] [0, 1, 1, 0, 0, 0, 0] [0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1] [0, 1, 1, 0, 0, 0, 1] [0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1] [0, 1, 1, 0, 0, 1, 0] [1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0] [0, 1, 1, 0, 0, 1, 1] [1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0] [0, 1, 1, 0, 1, 0, 0] [1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1] [0, 1, 1, 0, 1, 0, 1] [1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1] [0, 1, 1, 0, 1, 1, 0] [1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1] [0, 1, 1, 0, 1, 1, 1] [1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1] [0, 1, 1, 1, 0, 0, 0] [1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1] [0, 1, 1, 1, 0, 0, 1] [1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0] [0, 1, 1, 1, 0, 1, 0] [1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1] [0, 1, 1, 1, 0, 1, 1] [1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1] [0, 1, 1, 1, 1, 0, 0] [1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0] [0, 1, 1, 1, 1, 0, 1] [1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0] [0, 1, 1, 1, 1, 1, 0] [1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1] [0, 1, 1, 1, 1, 1, 1] [1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1] [1, 0, 0, 0, 0, 0, 0] [1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1] [1, 0, 0, 0, 0, 0, 1] [1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1] [1, 0, 0, 0, 0, 1, 0] [1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1] [1, 0, 0, 0, 0, 1, 1] [1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0] [1, 0, 0, 0, 1, 0, 0] [1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [1, 0, 0, 0, 1, 0, 1] [1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1] [1, 0, 0, 0, 1, 1, 0] [1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0] [1, 0, 0, 0, 1, 1, 1] [1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0] [1, 0, 0, 1, 0, 0, 0] [1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1] [1, 0, 0, 1, 0, 0, 1] [1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1] [1, 0, 0, 1, 0, 1, 0] [1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1] [1, 0, 0, 1, 0, 1, 1] [1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1] [1, 0, 0, 1, 1, 0, 0] [1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1] [1, 0, 0, 1, 1, 0, 1] [1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0] [1, 0, 0, 1, 1, 1, 0] [1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1] [1, 0, 0, 1, 1, 1, 1] [1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1] [1, 0, 1, 0, 0, 0, 0] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0] [1, 0, 1, 0, 0, 0, 1] [1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0] [1, 0, 1, 0, 0, 1, 0] [1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1] [1, 0, 1, 0, 0, 1, 1] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1] [1, 0, 1, 0, 1, 0, 0] [1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1] [1, 0, 1, 0, 1, 0, 1] [1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1] [1, 0, 1, 0, 1, 1, 0] [1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1] [1, 0, 1, 0, 1, 1, 1] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0] [1, 0, 1, 1, 0, 0, 0] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [1, 0, 1, 1, 0, 0, 1] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1] [1, 0, 1, 1, 0, 1, 0] [1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0] [1, 0, 1, 1, 0, 1, 1] [1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0] [1, 0, 1, 1, 1, 0, 0] [1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1] [1, 0, 1, 1, 1, 0, 1] [1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1] [1, 0, 1, 1, 1, 1, 0] [1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1] [1, 0, 1, 1, 1, 1, 1] [1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1] [1, 1, 0, 0, 0, 0, 0] [1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1] [1, 1, 0, 0, 0, 0, 1] [1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0] [1, 1, 0, 0, 0, 1, 0] [1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1] [1, 1, 0, 0, 0, 1, 1] [1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1] The program would output fourteen logical expressions (one for each column in the output). Is there a program that can do this for me? If not, how would you assume is the best way to do it? It doesn't have to be perfectly optimized logic, but that would surely help. An example of what the program could do: INPUT OUTPUT [0, 0] [1] [0, 1] [0] [1, 0] [0] [1, 1] [0] Then the program would output: A2 = A1 nor B1 A way to look at it is one expression for each column in the output. So all that has to be made sure is that the seven inputs in my first example, can achieve all the results in _X_ column of the output with a certain logical expression. Then this is repeated for all the columns in the output table. |
|
|
|
|
|
#2 |
|
Hobbyist Programmer
|
Could just be something to do with what i just smoked and maybe im in way over my head here; But where's there any f****** in what you posted?
__________________
Mona Lisa must of had the highway blues you can tell by the way she smiles.. |
|
|
|
|
|
#3 | ||
|
Professional Programmer
|
Quote:
__________________
▄▄▄▄ Quote:
Due to incorrect calculations during the middle ages, our calendar actually begins a few years after Jesus' birth. Thus the real 6/6/6 happened a few years back. The world already ended and you missed it. Download Code::Blocks now! ▄▄▄▄ |
||
|
|
|
|
|
#4 |
|
Hobby Coder
Join Date: May 2006
Posts: 57
Rep Power: 0
![]() |
IMO, you need to seriously back off the details, and give us a LOT more overview.
You show a VERY over-detailed input/output table, and then immediately jump into a different input/output, with A1, B1, but no clue as to exactly WHAT A1 or B1, IS? Yes, I can hypothesize what you may have meant, but if you want help, you're going to have to be a LOT more descriptive, here. Give us a SMALL example, step by step. In addition to helping us understand your problem, it may well help you further understand it, as well. We don't need sixy lines of input/output, but we need more lines of descriptive, step by step, notation. Adak |
|
|
|
|
|
#5 |
|
Programming Guru
![]() |
I assume if you don't know enough to understand my issue and proposed solution, then you don't know enough to help me. I explained to a reasonable extent what needs to be accomplished, and I'm asking you what you think should be done "step by step".
I've developed a good chunk of framework for this program, let me know if you think I'm doing anything wrong. This is in Python. What it does is starts with the smallest number of columns in the input side to try to minimilize the inputs that the logical expression uses. If this column does not satisfy enough unique inputs to outputs, then it proceeds to the next combination of column(s). When it finds a combination that does not have more then one output for the same input, validate() returns true and outputs the corresponding column of bits. If you run this program, you can see that for the "or" truth table, that the smallest number of columns possible to achieve a "validated" possibility of succeeding a logical expression, is both columns combined. This can be used to limit the possibilities, and also catch any obvious methods straight off the bat. IN SHORT... it tells you what input columns could (and should) be used to determine the "_output'th" output column, in order from smallest to greatest number of bits. Feel free to add and/or modify accordingly. class keep_index:
"""custom integer that can be called for its index value,
easiest way to attach a static value to a dynamic value"""
def __init__(self, value, index):
self.value = str(value)
self.index = index
def __call__(self):
return self.index
def __repr__(self):
return self.value
def __lt__(self, other):
return self.value < other
def __le__(self, other):
return self.value <= other
def __eq__(self, other):
return self.value == other
def __ne__(self, other):
return self.value != other
def __gt__(self, other):
return self.value > other
def __ge__(self, other):
return self.value >= other
def index_table(table):
"""add the index of each item in the table"""
ntable = []
for row in table:
ntable += [[[]]]
for i, item in enumerate(row[0]):
ntable[-1][-1].append(keep_index(item, i))
ntable[-1].append(row[1])
return ntable
def comb_list(seq, k):
""" Algorithm by Gilward Kukel
http://www.programmingforums.org/forum/showthread.php?t=4343
returns a list of all k-combinations
of the elements of sequence seq"""
n=len(seq)
if not 0<=k<=n:
raise Exception,"0<=k<=len(seq) is not true"
v=[] #list of combinations
#x: number of taken elements
#y: number of rejected elements
#we want to take k elements and reject n-k elements
def f(x,y,a):
if x==k:
#we have taken enough elements, reject all remaining elements
v.append(a)
return
if y==n-k:
#we have rejected enough elements, take all remaining elements
a.extend(seq[x+y:])
v.append(a)
return
if (x<k):
#take element seq[x+y]
h=a+[seq[x+y]]
f(x+1,y,h)
if (y<n-k):
#don't take element seq[x+y]
f(x,y+1,a)
f(0,0,[])
return v
def fetch(table, b):
"""fetch a column from the table"""
'''
[
[[(0, 0), (0, 1)], [(0, 0), (2, 2)], [(0, 1), (2, 2)]],
[[(0, 0), (1, 1)], [(0, 0), (2, 2)], [(1, 1), (2, 2)]],
[[(1, 0), (0, 1)], [(1, 0), (2, 2)], [(0, 1), (2, 2)]],
[[(1, 0), (1, 1)], [(1, 0), (2, 2)], [(1, 1), (2, 2)]]
]
'''
t = []
for row in table:
t.append([])
for item in row[b]:
t[-1].append(item)
return t
def validate(col, out):
"""find out if a logical expression is possible for this
column(s) (if there are two results for the same input)"""
'''
[[0, 0], [0, 1], [1, 0], [1, 1]], [0, 1, 1, 1]
'''
for find, flp in enumerate(col):
for sind, slp in enumerate(col):
if flp == slp and find != sind:
if out[find] != out[sind]:
return False
return True
def main(table):
INPUTS = len(table[0][0])
OUTPUTS = len(table[0][1])
ntable = index_table(table)
# figure out each output column one by one
for _output in range(OUTPUTS):
# grab the output column from the table
out = [row[1][_output] for row in ntable]
# we can't go past "INPUT" number of columns in the expression
for _input in range(1, INPUTS+1):
choices = []
for row in ntable:
# get all combination of elements inside a
# row that is _input'th elements long
choices += [comb_list(row[0], _input)]
for choice in range(len(choices[0])):
# fetch the column of each combination
columns = fetch(choices, choice)
# validate it with the "vertical line test"
if validate(columns, out):
print columns
if __name__ == '__main__':
table = [[[0, 0], [0]],
[[0, 1], [1]],
[[1, 0], [1]],
[[1, 1], [1]]]
main(table)Last edited by Sane; Jun 2nd, 2006 at 10:21 PM. |
|
|
|
|
|
#6 |
|
Programming Guru
![]() |
Okay. I have an example of what the program would do for my original truth table.
Y = OR(A, NOR(OR(AND(NOT(C), AND(B, D)), AND(OR(NOR(E, F), AND(AND(NOT(E), F), NOT(B))), AND(C, NOT(D)))), AND((AND(AND(NOT(C), D), OR(E, F))), NOT(B)))) That's what it would output for the first logical expression. As each number in the first output column can be satisfied by these conditions. I figured it out in my head, and I couldn't even start explaining how I did it. It would be very tough to program this I think. I would think someone has already though. If you'd like to test that equation, it is wrtten in Python using these functions... def AND(x, y):
return (x and y)
def NAND(x, y):
return not AND(x, y)
def OR(x, y):
return (x or y)
def NOR(x, y):
return not OR(x, y)
def XOR(x, y):
return (x or y) and (not (x and y))
def XNOR(x, y):
return not XOR(x, y)
def NOT(x):
return not x |
|
|
|
|
|
#7 | |
|
Hobbyist Programmer
|
Quote:
__________________
Mona Lisa must of had the highway blues you can tell by the way she smiles.. |
|
|
|
|
|
|
#8 |
|
Resident Grouch
![]() ![]() ![]() ![]() ![]() ![]() Join Date: Jun 2005
Posts: 6,453
Rep Power: 10
![]() |
You not only missed a word, you missed seeing that there's logic involved, somehow. Perhaps your definition of logic is limited.
__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code. Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers |
|
|
|
|
|
#9 |
|
Hobbyist Programmer
|
Perhaps my definition of logic is limited or maybe its my lack of knowledge of algebra IF im correct in thinking this is part of what it entails?
__________________
Mona Lisa must of had the highway blues you can tell by the way she smiles.. |
|
|
|
|
|
#10 |
|
Resident Grouch
![]() ![]() ![]() ![]() ![]() ![]() Join Date: Jun 2005
Posts: 6,453
Rep Power: 10
![]() |
__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code. Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers |
|
|
|
![]() |
| Bookmarks |
| Currently Active Users Viewing This Thread: 1 (0 members and 1 guests) | |
| Thread Tools | |
| Display Modes | |
|
|