Thread: Logical Operators

Really no idea if this is the right section or not so apologies if it isn't, this section was my best guess.

The question comes in two parts:

i) A 2-ary logical operator takes two propositions, P1 and P2, and gives a truth value depending on the truth values of P1 and P2. Conjunction and disjunction are examples of 2-ary operators. How many 2-ary operators are there? Explain.

ii) A k-ary operator takes k propositions, P1.... Pk. How many k-ary operators are there? Explain your answer.

For the first part if I interpret the question right then my answer would be four (conjunction, disjunction, implication and equivalence).

The second part I'm completely baffled on, it's not so much how to do the question that's troubling me but more what is being asked. I was in a class where the question was being discussed and I overheard that 2^2k was close to the answer and I don't see how the question is asking for anything like that. It's also made me doubt my answer to the first question. Wondering if my understanding of the terms is a bit off.

Thanks for any help!

Originally Posted by anonymouse

Really no idea if this is the right section or not

The right subforum for such questions is Discrete Math.

Originally Posted by anonymouse

i) A 2-ary logical operator takes two propositions, P1 and P2, and gives a truth value depending on the truth values of P1 and P2. Conjunction and disjunction are examples of 2-ary operators. How many 2-ary operators are there? Explain.

For the first part if I interpret the question right then my answer would be four (conjunction, disjunction, implication and equivalence).

What about the operator that returns the truth value of the first proposition and ignores the second one? What about the negation of the second proposition? The negation of conjunction, disjunction?

Originally Posted by anonymouse

ii) A k-ary operator takes k propositions, P1.... Pk. How many k-ary operators are there? Explain your answer.

This is easy to answer if you are familiar with truth tables. Since there are k arguments and one result, each row of the table has k + 1 truth values, the last of which is determined by the first k (given the operator, of course). How many rows are there? They must contain all possible combinations of k truth values. There are two possible values for the first argument; for each of those there are two possible values for the second argument, and so on.

Now, suppose there are n rows where n is a function of k. How many ways are there to fill the last column of the truth table, which determined the value of the operator on those k arguments? For each of the n slots, there are two options.

Logical Operators

Logical Operators
Example Name Result
$a and $b And TRUE if both $a and $b are TRUE.
$a or $b Or TRUE if either $a or $b is TRUE.
$a xor $b Xor TRUE if either $a or $b is TRUE, but not both.
! $a Not TRUE if $a is not TRUE.
$a && $b And TRUE if both $a and $b are TRUE.
$a || $b Or TRUE if either $a or $b is TRUE.
Some information if you wanted on different topic like Prime Numbers of mathematics ,wikipedia is best.

boolean binary operators (ones that take propositions, or more generally well-formed formulas) as inputs, and return truth-values as outputs (where the set of truth values is usually restricted to {true,false}) can be thought of as functions from the set {0,1} x {0,1} to the set {0,1} (this is essentially what a truth table is). usually "1" is identified with "true" and "0" identified with "false".

in general, the cardinality of the set of functions f:A→B is |B|^|A|.

since |{0,1}| (or |{true,false}|) = 2. and the cardinality of AxB is |A|*|B|,

the number of binary boolean operators is 2^2*2 = 16. they even have (mostly) names:

constant truth (output is always true, no matter what the input)
constant falsity (output is always false)

there are 4 binary operations that "ignore one input", these are essentially unary operators "padded with a dummy variable" (and often replaced with "not"):

(true if the first is true, false if the first is false) or "A"
(false if the first is true, true is the first is false) or "not A"
(true if the second is true, false if the second is false) or "B"
(false if the second is true, true if the second is false) or "not B"

or (disjunction/inclusive or)
if (reverse implication)
implies (only if/if...then)
if and only if (biconditional/equivalence)
and (conjunction)
nand (not and)
xor (exclusive or/not equivalent)
nimp (not implies)
nif (not if)
nor (not or)

as you can see the first five have a certain linguistic precedence, while the latter five are primarily described in terms of negating one of the first five.

we can easily compute the number of k-ary operations (k inputs) in a similar fashion:

such an operation is a function {0,1}^k→{0,1} and so there are 2^(2k) possible.