Answers to test yourself questions in Connectives handout.

1. Draw the Hasse diagrams using |=^s for the languages L₁, L₂ and L₃.

a. L₁.

   a     b
    \   /
     \ /
      e

b. L₂.

    aa   ab    bb
     \   / \   /
      \ /   \ /
       a     b
        \   /
         \ /
          e

c. L₃.

 aaa  aab   abb  bbb
  \   / \   / \   /
   \ /   \ /   \ /
    aa    ab   bb
     \   / \   /
      \ /   \ /
       a     b
        \   /
         \ /
          e

2. What is the conjunction of a with b in each of the systems in 1?

• a & b = e in each of the systems in 1.

3. In which of the systems in 1 is the conjunction of ab with bb defined? What is it for each system in which it is defined?

• L₂ and L₃. In both systems, ab & bb = b.

4. Is the conjunction of every pair of members of every L_n defined? Why or why not?

• Yes. The conjunction of every pair of members in every L_n is their longest common substring, which is always unique.

5. In which of the systems in 1 is the disjunction of a with b defined? What is it for each system in which it is defined?

• L₂ and L₃. In both systems, a | b is ab. In L₁, both a and b are candidates, but neither is weaker than the other.

6. Is the disjunction of every pair of members of L defined? Why or why not?

• Yes. Let a^hbⁱ and a^jb^k be a pair of members of L, and let p = max(h, j) and q = max(i, k). Then a^hbⁱ | a^jb^k = a^pb^q. On the other hand, for any sublanguage L_n, a^hbⁱ | a^jb^k is undefined if p+q is greater than n.

7. What is the negation of a in each of the systems in 1?

• In L₁, ~a = b. In L₂, ~a = bb. In L₃, ~a = bbb.

8. In L₂ and L₃ the double negation of a is distinct from a. What is it in each case?

• In L₂, ~~a = aa. In L₃, ~~a = aaa.

9. Draw the Hasse diagrams using |=^s for the languages M₁ and M₂.

a. M₁

   a     b
    \   /
     \ /
      e

b. M₂

  aa   ab  ba    bb
   \    /\ /\    /
    \  / / \ \  /
     \//     \\/
      a       b
       \     /
        \   /
         \ /
          e

10. What is the conjunction of a with b in each of the systems in 9?

• a & b = e in each of the systems in 9.

11. What is the conjunction of ab with bb in M₂?

• In M₂, ab & bb = b.

12. Why is the conjunction of ab with ba in M₂ not defined?

• Both a and b are candidates, but neither is weaker than the other.

13. Why is the disjunction of a with b in M₂ not defined?

• Both ab and ba are candidates, but neither is weaker than the other.

14. What is the negation of a in each of the systems in 9?

• In M₁, ~a = b. In M₂, ~a = bb.