(a) Let * be a Boolean operation defined as
If C = A * B then evaluate and fill in the blanks:
(i) A * A = _______
(ii) C * A = _______
(b) Solve the following boolean equations for the values of A, B and C:

Obtain the principal (canonical) conjunctive normal form of the propositional formula

  (p ∧ q) V (¬q ∧ r) 

Where ‘∧’ is logical and, ‘v’ is inclusive or and ¬ is negation.

Which one of the following predicate formulae is NOT logically valid?
Note that W is a predicate formula without any free occurrence of x.

What is the correct translation of the following statement into mathematical logic?

“Some real numbers are rational”

Consider the following logical inferences.

I1: If it rains then the cricket match will not be played.
The cricket match was played.
Inference: There was no rain.
I2: If it rains then the cricket match will not be played.
It did not rain.
Inference: The cricket match was played.

Which of the following is TRUE?

Which of the following is false? Read ∧ as AND, ∨ as OR, ~ as NOT, → as one way implication and ↔ as two way implication.

Which of the following propositions is a tautology?

What is the converse of the following assertion?

  I stay only if you go. 

(a) Show that the formula [(~p ∨ q) ⇒ (q ⇒ p)] is not a tautology.
(b) Let A be a tautology and B be any other formula. Prove that (A ∨ B) is a tautology.

Let a, b, c, d be propositions. Assume that the equivalence a ↔ (b ∨ -b) and b ↔ c hold. Then the truth-value of the formula (a ∧ b) → (a ∧ c) ∨ d is always

Consider two well-formed formulas in prepositional logic

   F1: P ⇒ ¬P          F2: (P⇒¬P)∨(¬P⇒P)  

Which of the following statements is correct?

“If X then Y unless Z” is represented by which of the following formulas in prepositional logic? (“¬“, is negation, “∧” is conjunction, and “→” is implication)

The following resolution rule is used in logic programming.

Derive clause (P ∨ Q) from clauses (P ∨ R), (Q ∨ ¬R) 

Which of the following statements related to this rule is FALSE?

Consider the following formula a and its two interpretations I₁ and I₂

α: (∀x)[Px ⇔ (∀y)[Qxy ⇔ ¬Qyy]] ⇒ (∀x)[¬Px]
I1: Domain: the set of natural numbers
    Px ≡ 'x is a prime number'
    Qxy ≡ 'y divides x'
I2: same as I1 except that Px = 'x is a composite number'.

Which of the following statements is true?

Which of the following is a valid first order formula? (Here α and β are first order formulae with x as their only free variable)

Show that proposition C is a logical consequence of the formula

     A ∧ (A →(B ∨ C)) ∧ (B → ~A)  

Using truth tables.

(a) Uses Modus ponens (A, A →|= B) or resolution to show that the following set is inconsistent:

 (1) Q(x) → P(x)V ~ R(a)
 (2) R(a) ~ Q(a)
 (3) Q(a)
 (4) ~ P(y) 

Where x and y are universally quantified variables, a is a constant and P, Q, R are monadic predicates.

(b) Let S be the set of all integers and let n > 1 be a fixed integer. Define for a, b ∈ S, a R biff a-b is a multiple of n. Show that R is an equivalence relation and finds its equivalence classes for n = 5.

Consider the following first order logic formula in which R is a binary relation symbol.

 ∀x∀y (R(x, y)  => R(y, x)) 

Which one of these first-order logic formula is valid?

Which of the following first order formula is logically valid? Here α(x) is a first order formula with x as a free variable, and β is a first order formula with no free variable.

Which of the following is the negation of [∀x, α →(∃y, β →(∀ u, ∃v, y))]

Which of the following well-formed formulas are equivalent?

Choose the correct alternatives (More than one may be correct). Indicate which of the following well-formed formulae are valid:

The following propositional statement is (P → (Q v R)) → ((P v Q) → R)

Identify the correct translation into logical notation of the following assertion.

      "Some boys in the class are taller than all the girls"  

Note: taller(x,y) is true if x is taller than y.

Which one of the following well formed formulae is a tautology?

Which one of the following well-formed formulae in predicate calculus is NOT valid?

Consider the first order predicate formula φ:

∀x[(∀z z|x ⇒ ((z = x) ∨ (z = 1))) ⇒ ∃w (w > x) ∧ (∀z z|w ⇒ ((w = z) ∨ (z = 1)))]

Here 'a|b' denotes that 'a divides b', where a and b are integers. Consider the following sets:

S1.  {1, 2, 3, ..., 100}
S2.  Set of all positive integers
S3. Set of all integers

Which of the above sets satisfy φ?

P and Q are two propositions. Which of the following logical expressions are equivalent?

I. P∨∼Q
II. ∼(∼P∧Q)
III. (P∧Q)∨(P∧∼Q)∨(∼P∧∼Q)
IV. (P∧Q)∨(P∧∼Q)∨(∼P∧Q)

Let fsa and pda be two predicates such that fsa(x) means x is a finite state automaton, and pda(y) means that y is a pushdown automaton. Let equivalent be another predicate such that equivalent (a, b) means a and b are equivalent. Which of the following first order logic statements represents the following:

Each finite state automaton has an equivalent pushdown automaton

Let P, Q and R be three atomic prepositional assertions. Let X denote (P ∨ Q) → R and Y denote (P → R) ∨ (Q → R). Which one of the following is a tautology?