# Discrete Mathematics - Truth Function Problem

I keep trying to reason how is letter C the answer to this question, but I can't fully understand how can one find the solution to this type of problems. What I understand:

• There's 2 arguments in the given truth function, therefore we have 2^(2) = 4 total statements. This is because we have f(x, y) = k. In the case we had 3 arguments/variables, then we would have f(x, y, z) = k.

• The f( T, F) = T is the only statement that results true for when the values T, F are assigned to the respective variables. (i.e. In the case P = T and Q = F, or Q = T, and P = F).

• For any compound statement the function F(T, F) has to result in true.

The algorithm for TRUE function:

Input: A truth function F with an n number of arguments x_1, x_2, x_3, ..., x_n.

Output: A statement S whose truth function is f. This statement can only involve the connectives of conjunction "AND", disjunction "OR" , and negation "~".

Step 1:

Consider a basic statement q_i for each argument x_i of f, where i = 1,2,3, .., n.

Step 2:

For each combination of values for the arguments x_1, x_2, x_3, ..., x_n. Consider the statement:

S_j = P^(1)_j "AND" P^(2)_j "AND"... "AND" P^(n)_j.

where, P^i _ j {

q_i IF x_i = T

~q_i IF x_i = F

}

Step 3:

Let J_1, J_2, J_3, ..., J_k. Be the index for the combination of values for x_1, x_2, x_3, ..., x_n that force f to produce T.

S = S_ J_1 "OR" S_ J_2 "OR" S_ J_3

CLAIM I: Every statement S_J is only true for the combination of values that we used to construct it.

CLAIM II: For each combination of values, there is only one S_J that is true for that combination.

PICTURE OF THE PROBLEM HERE:

https://imgur.com/a/jnMckeM

Sorry for the notation, I don't know any text editors for this sort of syntax. I hope is readable.

The problem uses $$f(p,q)$$, so $$p$$ is the first argument, and $$q$$ the second. So, the truth table shows that the only case where $$f$$ returns True is if $$p=T$$ and $$q=F$$. If $$q=T$$ and $$p=F$$ then $$f(p,q)=F$$. So, what you have at the very end of the second bullet point is wrong. (And maybe now it is easier to see what the correct answer is!)
• @ChalupaBatmac Yes, it is assumed that $p$ refers to the first argument, and $q$ to the second. – Bram28 Nov 19 '18 at 16:27