University Homework: Logic, Regular Expressions and Truth Tables

This homework assignment focuses on fundamental concepts in logic and regular expressions. The solutions cover multiple-choice questions that test the understanding of regular expressions, including identifying valid and invalid strings based on given patterns. The assignment also includes problems on propositional logic, requiring the calculation of truth values for compound propositions and the use of truth tables to determine if a proposition is a tautology or a contradiction. Furthermore, the solutions demonstrate the application of inference rules to prove logical arguments. Overall, the assignment assesses the ability to apply theoretical knowledge to solve problems related to logic, regular expressions, and their applications in computer science.

Question 1 (1 point)
Which of the following are not strings in the language defined by the regular
expression
a b+ c{2} d?
(Choose all that apply)
Question 2 options:
abcd
abbccdd
abbbcc
bccd
Question 2 (1 point)
Use truth tables to determine whether the following proposition is a tautology or a
contradiction:
p => (q => p)
Truth table
p q Q=>p P=>(q=>p
)
tautology contradictio
n
T T T T T F
T F T T T F
F T F F T F
F F F F T F
P=> (q=>p) is neither a tautology nor contradiction.
Question 6 options:
Tautology
Contradiction
Question 3 (1 point)
Calculate the truth value of the following proposition:
(1 < 0) ⋀ (2 < 1)

Let (1<0) be A which is a false statement and
(2<1) be B is also a false statement
Therefore:
(A) ⋀ (B) => (F) and (F)
Which always give a false (F).
Question 7 options:
True
False
Question 4 (1 point)
Calculate the truth value of the following proposition:
(0 < 1) ⋀ (1 < 2)
Let (0<1) be A and (1 < 2) be B
A is a true statement while B is a true statement also.
Therefore:
A ⋀ B results in a true value.
Question 10 options:
True
False
Question 5 (1 point)
Which of the following are valid strings as defined by this regular expression
[bc]+at
(Choose all that apply)
Question 11 options:
cat
catbat

at
bcat
Question 6 (1 point)
Calculate the truth value of the following proposition:
(0 < 1) ⋁ (1 < 2)
Let (0 < 1) be X and (1 < 2) be Y;
X and Y are true statements therefore:
X ⋁ Y gives a true value.
Question 12 options:
True
False
Question 7 (1 point)
Use the Inference Rules given in lecture 15-16 to prove the following logical
argument:
P ⋀ ¬Q, P -> (R and S) |- R
Which rules were used? (In the order shown)
Question 13 options:
Rule 5a (If-then elimination), Rule 1 (And Introduction), Rule 2 (And elimination)
Rule 5a (If-then elimination), Rule 2 (And elimination), Rule 2 (And elimination)
Rule 2 (And elimination), Rule 2 (And elimination), Rule 5a (If-then elimination)
Rule 2 (And elimination), Rule 5a (If-then elimination), Rule 2 (And elimination)
Question 8 (1 point)

Which of the following are strings in the language defined by the regular
expression
a b+ c{2} d?
(Choose all that apply)
Question 15 options:
abcc
accd
abbccd
abbccdd
Question 9 (1 point)
Which of the following statements are simple propositions? (Choose all that
are)
Question 17 options:
There is nothing on the television
It is not raining today
Thursday is the day before Friday
The earth revolves around the moon
Question 10 (1 point)
Which of the following strings are not in the language defined by the regular expression
a((a∪b)∗c)∗
Choose all that apply
Question 18 options:
ab
ac
babc
cbabc

Question 11 (1 point)
Which of the following sentences are compound propositions (choose all that
are)
Question 19 options:
I am not singing
Tomorrow is another day
My dog likes barking
I go dancing on Saturday and running on Sunday