logical associative expressiveness with no negation operator

172 Views Asked by At

Let's suppose we can only use $\wedge$ and $\vee$ operators (we have no negation operator), and by default we have associativity to the left.

Is this subset of logic as expressive as the one with the default operator prevalence ( $\wedge$ higher than $\vee$ )?

I thought they were going to be equivalent but I'm not able to transform this simple expression to a left associative logic.

A $\wedge$ B $\vee$ C $\wedge$ D

2

There are 2 best solutions below

1
On BEST ANSWER

A left-associated expression that ends $\ldots\lor X$ is true whenever $X$ is true, and one that ends $\ldots\land X$ is true only when $X$ is true; the formula $A\land B\lor C\land D$ does not have either property with respect to any of its variables when interpreted with $\land$ having precedence over $\lor$, so it is not equivalent to any left-associated expression.

(I am assuming that you don't have parentheses, as otherwise priority of operations imposes no real constraint.)

0
On

Take your particular example. Then it's easy to see that

$$A\land (B\lor (C\land D)) \tag{1} $$

$$(A\land B)\lor (C\land D) \tag{2} $$

are not equivalent (Hint: fix $(C\land D)$, call it say '$\alpha$'. Then draw a simple truth table)