1
vote
1answer
48 views

unary propositional connective

Let F be a unary propositional connective, such that F(p) is always false, regardless of the value assigned to p. i. Give the truth table for F. (Hint: how many lines does it have?) I have: p | ...
0
votes
1answer
136 views

Propositional Logic - induction

(a) Let C be the set {∧,∨} of propositional connectives, and let P be any set of propositional variables. i. Suppose that: φ is a well-formed formula that uses only connectives in C and variables ...
1
vote
1answer
35 views

Can kCNF have less than k variables per clause?

An example given by my prof in her notes: The following formula is in 4CNF: $(w\vee y\vee \neg z)\wedge(w\vee\neg x\vee z)\wedge(w\vee\neg x\vee \neg y\vee z)$ I originally thought that maybe ...
1
vote
2answers
164 views

How to find an equivalent formula?

I have a formula: $p \wedge \neg q \implies q \vee \neg p $, and i have calculated a truth table as follows: $$\begin{array}{c} p&q&\text{Formula}\\ \hline 0&0&1\\ 0&1&1\\ ...
3
votes
0answers
297 views

Constructor And\Or-graph on function transition of the alternating automata

In a And\Or-graph induced by the transition function, each node of G corresponds to a state q belonging to set Q of the state of the Automaton, for q with $\delta(q,a)=q1*q2$, the node is a $*-node$ ...