Questions tagged [propositional-calculus]

Appropriate for questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions. Also for general questions about the propositional calculus itself, including its semantics and proof theory. Questions about other kinds of logic should use a different tag, such as (logic), (predicate-logic), or (first-order-logic).

Propositional logic is a branch of logic dealing with logical connectives and statements involving them. A logical connective connects finitely many sentences and forms a compound sentence, in a way that the truth value of the compound sentence depends only on the truth value of its constituents. The most common connectives are the binary connectives conjunction ($\land$), disjunction ($\lor$) and implication ($\rightarrow$), the unary connective negation ($\neg$), and the nullary connectives true ($\top$) and false ($\bot$).

Any proposition is considered to be either atomic (in which case it has no constituents) or compound (in which case it's formed by mean a connective using simpler propositions). A propositional model is a function assigning to each atomic proposition a truth value $0$ or $1$. The truth values of compound propositions are then determined by the truth values of their constituents. For example, if $I$ is a function assigning truth values to propositions, one would have $I(\top)=1$, $I(\bot)=0$, $I(\neg A)=1-I(A)$, $I(A\land B)=\min\big(I(A),I(B)\big)$, $I(A\lor B)=\max\big(I(A),I(B)\big)$ and $I(A\rightarrow B)=\max\big(1-I(A),I(B)\big)$. The propositions having the value $1$ for every model, are called tautologies, and those having the value $0$ for every model, are called absurdities. A central task of propositional logic is characterizing tautologies and absurdities.

5541 questions
1
vote
2 answers

What is the logic symbol to write: $D$ only when $P$

The text I am reading gives this problem: Express the following using logic symbols. The cat is out of the bag only when the contestant is bald. $D$ is: The cat is out of the bag, and $P$ is: The contestant is bald, thus $D$ only when $P$. I…
user756686
1
vote
0 answers

Is this minimal complete system?

In propositional logic, I know that this natural deduction system is complete: Rules of inference: MP, Abs, Simp, Add Rules of replacement: DM, Com, Assoc, Dist, DN, Impl, Equiv But I want to know: is this minimal? i.e., is it still complete if one…
Idiot
  • 23
1
vote
3 answers

Is $A \to \neg A$ logically satisfiable if $A$ is false?

Is it true that the implication $A \to \neg A$ is logically satisfiable if $A$ is false? I beg your pardon if it is trivial but my logic is rusty.
1
vote
1 answer

How can $(\lnot q \lor r)$ become $(p \to r)$ in this context?

Question Show that $(p\lor q)\rightarrow r\equiv(p\rightarrow r)\land(p\rightarrow r)$ Given solution While I was taught that $(p\rightarrow r)\equiv( \neg p\lor r)$ which can be easily proven by a truth table... but how is the last 2 statements…
terahertz
  • 279
1
vote
1 answer

NEGATE this statement: if $L(M) = \emptyset$, then for any $w$, $M$ halts on $w$ implies $M$ loops on $ww$

if $L(M) = \emptyset$, then for any $w$, $M$ halts on $w$ implies $M$ loops on $ww$ M is a turing machine. my attempt First I'm trying to simplify this using $A \to B = not A \lor B$ $\Leftrightarrow L(M) \neq \emptyset$ or for all $w$, $M$ halts on…
Tree Garen
  • 709
  • 5
  • 15
1
vote
1 answer

Name for this family of operations

Given some True / False propositions $A,B,C,D, \dots$ I would like to know if there is a name for these operations: $ONE(A,B,C)$ - true if exactly one of $A, B$ and $C$ is true, false otherwise $TWO(A,B,C)$ - true if exactly two of $A, B$ and $C$ is…
Ben Crossley
  • 2,544
1
vote
1 answer

Boolean logic simplification of $a * b' * c' * d' + a * b + b * d' + b * c * d$

The expression $a * b' * c' * d' + a * b + b * d' + b * c * d $ becomes $a * b + a * c' * d' + b * c + b * d'$, but how can I show that? I can find any laws to solve this. Thanks in advance.
1
vote
1 answer

Why is propositional logic often considered just a "toy"?

I recently posted a question on the relation between triviality and decidability in a logic. As a footnote to that post, I added that propositional logic is often considered just a "toy". The answer to that post gives a brief comment about…
1
vote
1 answer

Equivalent sets of wffs

Propositional logic. Given two sets of wffs, $\Sigma$ and $\Gamma$, are the following definitions of equivalence between $\Sigma$ and $\Gamma$ .....equivalent? $(\Sigma\vDash\Gamma)\land(\Gamma\vDash\Sigma)$ For all $\alpha$,…
1
vote
1 answer

What is the negation of $p\to \sim q$?

I know that the negation of $p\to q$ is ~p V q but I can’t seem to figure out the effect $\sim q$ will have on the negation. Also is their a way to check if something is the negation of a statement?
Mikayla
  • 19
1
vote
2 answers

Contrapositive of $p\land q \implies r$

Now I understand that strictly speaking the contrapositive of this statement would be $\neg r \implies \neg p\lor\neg q$, but what I would like to do instead is prove that $\neg r\land q \implies \neg p$. What I'm asking is, can I still call this a…
1
vote
1 answer

As I got the contrapositive of this statement, how does e) necessarily follows from this?

An electronic circuit contains three light bulbs, X, Y and Z, which are each either on or off at any particular time. It is known that if bulb X is off or bulb Y is on, then bulb Z is on. Which one of these statements necessarily follows from…
Kevin
  • 101
1
vote
2 answers

Transform $(\phi \vee \psi) \wedge (\neg \phi \vee \neg \psi) $ to $ (\phi \wedge \neg \psi) \vee (\neg \phi \wedge \psi)$ using equivalences?

$(\phi \oplus \psi) \equiv (\phi \vee \psi) \wedge (\neg \phi \vee \neg \psi) \equiv (\phi \wedge \neg \psi) \vee (\neg \phi \wedge \psi)$ I found the first one in a book and thought of the second one myself and was under the impression that I can…
steve
  • 639
  • 1
  • 5
  • 8
1
vote
3 answers

Logical equivalence of ¬p→q

Just wondering what other ways $\neg p \to q$ can be expressed. I know that $p\to q$ is logically equivalent to $\neg p\lor q$, hence I think that $\neg p\to q$ has the same logical equivalence as $p\lor q$.
1
vote
0 answers

Solving Propositional Calculus

"If Jimmy takes the Math Class, Jimmy will lose his weight. If Jimmy takes the Music Class, Jimmy will lose his hair. Jimmy will take the Math Class and the Music Class. Therefore, Jimmy will lose weight and hair." Given these statements, I…