|
If any of you have taken a logic course, I'd ask you to give me a hand with this. I'll copy it verbatim.
Finding a Formula(a WFF) given its Truth Table.
Suppose I tell you the distribution of T's and F's under the main operator of a well formed formula; can you find a formula having that as its truth table? For example, suppose we consider a wff with three variables, p, q, and r, and I give you the following column under its main operator as: F, F, T, F, F, T, F, T. Now, find a wff compatible with this column.
Do you think that cleverness and ingenuity are required? Well, it so happens that there is a ridiculously simple mechanical method that solves all problems of this type! Once you realize the method, then regardless of the distribution of T's and F's in the main operator column, you can instantly write down the required formula.
Any help is appreciated!
|
United States24775 Posts
|
It's a little assignment for my propositional calculus-based logic course.
|
That does tease my brain, but I'm not to sure I understand the formulation.
F, F, T, F, F, T, F, T
are the evaluation of the formula for
pqr - pq/r - p/qr - p/q/r - /pqr - /pq/r - /p/qr - /p/q/r
Is that it or am I wrong?
|
I'm not entirely sure where you're going with that. Keep in mind the truth table takes into account every possible combination for the three variables. Also let it be noted that the "column under the main operator" speaks to the validity of the entire formula.
For example, if the equation was (p^q)-->r (p AND q) implies r
then if p^q is true and r is false, the validity of the formula would be an F. However, is p^q is true and r is true, or any other combination than the aforementioned, the validity of the formula, or the "column under the main operator" would be listed as T(for valid).
|
guess if you can find the algorithm with this hint
Assuming that this is the distribution
p q r | value
F F F | F
F F T | F
F T F | T
F T T | F
T F F | F
T F T | T
T T F | F
T T T | T
f(p, q, r) = (F and T and F) or (T and F and T) or (T and T and T)
|
On March 27 2009 01:52 StRyKeR wrote:
guess if you can find the algorithm with this hint
Assuming that this is the distribution
p q r | value
F F F | F
F F T | F
F T F | T
F T T | F
T F F | F
T F T | T
T T F | F
T T T | T
f(p, q, r) = (F and T and F) or (T and F and T) or (T and T and T)
That's what I thought too yes. Finding a WFF is just that easy, even though it can be ugly.
Finding an elegant and short one could indeed require more ingenuity. But not that much.
|
I came up with the following formula that fits:
(p --> r) AND ( NOT(p) --> NOT(q --> r))
which translates to:
(NOT(p) OR r) AND (p OR q) AND (p OR NOT(r))
Have no idea about an algorithm yet tho 
Edit: I guess the people that posted above have the algorithm sorted Just make an AND-structure that fits for every TRUE combination and combine them into an OR-sentence. I learned that trick some time ago, but I forgot 
|
|
|
On March 27 2009 02:27 imDerek wrote:
Use a K-map
Beat me to it,
|
Would you guys care to explain that algorithm and k-map?
|
On March 27 2009 02:42 Track wrote:
Would you guys care to explain that algorithm and k-map?
I guess you N E E D the help
On March 27 2009 01:52 StRyKeR wrote:
guess if you can find the algorithm with this hint
Assuming that this is the distribution
p q r | value
F F F | F
F F T | F
F T F | T =============> T
F T T | F
T F F | F
T F T | T =============> T or
T T F | F
T T T | T =============> T
-------------------------------------
f(p,q,r)= T
f(p, q, r) = (-p and q and -r) or (p and -q and r) or (p and q and r)
|
|
|
Baa?21244 Posts
So you guys are doing his homework for him? Didn't know TL changed its attitudes towards people asking for homework "help."
I got 2 LA papers and a physics lab that I'd be much obliged if ya'll would do for me, thanks you, come again.
|
This is pretty trivial stuff for anyone that's taken even an entry level course in logic/boolean algebra no?
|
is awesome32278 Posts
|
is awesome32278 Posts
On March 27 2009 03:56 Pawsom wrote:
This is pretty trivial stuff for anyone that's taken even an entry level course in logic/boolean algebra no?
yes
|
They're not doing my homework for me, smartass. I asked for help on a problem; that's hardly disallowed. And yeah, it's elementary logic because I'm in an elementary logic course in university.
|
On March 27 2009 07:29 Track wrote:
They're not doing my homework for me, smartass. I asked for help on a problem; that's hardly disallowed. And yeah, it's elementary logic because I'm in an elementary logic course in university.
I think people jumped on you because the title made it seem like it would be an interesting, challenging question that would provoke a lot of thought, and in reality, it was just a pretty basic homework problem.
|
On March 27 2009 04:04 IntoTheWow wrote:
KARNAUGHT MAPS!
wait, was that paragraph about "theres a simple method lulz" part of the question, or something that you are telling us? because if it's the latter, i don't see why you need help, but if it's the former, isn't it just a homework thread?
anyway k-maps rule
edit: wait nevermind i just noticed you said you copied it all verbatim.. so i guess it's just a hw thread. look up k-maps on wiki, learn how to construct them (make sure each side-by-side differ by one bit at the most.. dont do the rookie 00 01 10 11 mistake), and just group them and simplify. takes like 30 seconds
|
|
|
|
|
|
EPT![[image loading]](http://img56.imageshack.us/my.php?image=51226529.jpg)
