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
0 answers

Proving that a set is functionally complete

Now I have been researching this for the last couple of hours trying to understand this, looking at similar questions asked on Stack but I am still very confused. This question was asked by another user a while back: Show that a set of logical…
1
vote
1 answer

show that L+ is inconsistent

Let $A$ be a statement for which is not a tautology. Let $L^+$ be the formal theory obtained from $L$ by adding as new axioms all formulas obtainable from $A$ by substituting arbitrary statement forms for the statement letters in $A$, the same forms…
1
vote
1 answer

Stuck with this proof of an equivalence of two propositional calculus formulas

How do I prove that $$\neg(\neg p\to (q\wedge p)) \equiv p\to (\neg q\wedge \neg p)$$ Edit 1: I need to do this prove without using a truth table. A table does indeed show that they are equivalent, but I cannot think of any basic or derivative laws…
Bcr20c
  • 13
1
vote
1 answer

Can a logical transformation rule be applied when nested within a formula?

As an example, let's take the double negation elimination rule $$\neg \neg p\vdash p\ \ \ \text{and}\ \ \ p\vdash\neg \neg p$$ With this, we know that if $p$ is true, then $\neg\neg p$ is true, and vice versa. Now suppose we're given the formula…
Graviton
  • 4,462
1
vote
1 answer

Invalid form of an argument

Modus ponens, that is [(A→B) and A, therefore B], is a valid argument. If we use the form (1) [(A→B) and B, therefore A], the argument is no longer valid because for the assignment [A = False, B = True], we have the premises (A→B) and B both true…
1
vote
1 answer

What law of algebra of proposition is happening here?

I'm preparing for a test tomorrow and going over some reading material, and I came across this problem that was worked out. So far I think I'm following each step of logic, but I've hit a wall with this part: (p $\land$ ($\lnot$(r $\land$ q)))…
1
vote
0 answers

If A implies B and B is not a tautology, then the negation of A also implies B?

I wanted to ask you if the following claim is correct, assuming the principle of bivalence: "If $B$ is not a tautology and $A \models B$, then $ \lnot A \not\models B$" My reasoning is the following, indicating Models of $A, B$ with $Ma,Mb$ and with…
PwNzDust
  • 468
1
vote
1 answer

Contrapositive of: If $a_n > 0$ and $\sum a_n$ converges, then $\sum 1/a_n$ diverges.

I would like to find the contrapositive of: If $a_n > 0$ and $\sum a_n$ converges, then $\sum 1/a_n$ diverges. My first idea is to rewrite it symbolically: Let $a_n$ be a sequence of real numbers. $\forall i \in \mathbb{N}, a_i > 0 ~ \land \sum a_n$…
1
vote
1 answer

Replace propositional variables in $\phi$ by their negation, flip the truth value of result, and show result has the same truth value as $\phi$.

Let $\phi$ be a formula built with $\lnot,\ \land,$ and $\lor$. Let $\phi'$ be constructed by replacing each propositional variable from $\phi$ with its negation. For any truth assignment $v$, let $v'$ be the truth assignment that gives each…
John Glen
  • 185
1
vote
1 answer

Best way to eliminate an operand when attempting to prove propositional equivalence (without truth tables)

I have been attempting to prove the following proposition is a tautology, without the use of truth tables (i.e.: using logical equivalences): $(((a \land \lnot b) \lor \lnot c) \land (a \lor b)) \lor (c \lor \lnot b)$ The initial approach that…
Ryan
  • 13
  • 2
1
vote
1 answer

Logic: How does Distributive work if both the terms also have an And/Or argument?

I have $¬(¬(P ∧ ¬Q) ∨ (¬R ∨ ¬Q)),$ I know I can distribute to get: $¬((¬P ∨ Q) ∨ (¬R ∨ ¬Q))$ ... my question is a little basic but I don't know whether my next step will be: $(P ∧ ¬Q) ∨ (R ∧ Q)$ or $(P ∧ ¬Q) ∧ (R ∧ Q)$ I'm inclined to believe the…
Mike
  • 11
1
vote
1 answer

Propositional Calculus and associated problems

What I'm trying to prove: $P\to (Q\to S)$ Given Premises: $P\to (Q\to R)$ and $Q\to (R\to S)$ My approach: $$Q\to (R\to S)$$ $$(Q\land R)\to S$$ $$(R\land Q)\to S$$ $$R\to (Q\to S)$$ also from the premises, $$P\to (Q\to R)$$ $$(P\land Q)\to…
Nimrod
  • 155
1
vote
1 answer

Simplifying a propositional formula

I have the following logical expression to solve/Simplify. Anyone able to help please?? $(P\land Q\land R)\lor (P\land\lnot Q\land R)\lor (P\land \lnot Q\land \lnot R)$
user10695
  • 655
1
vote
1 answer

Boolean function that checks whether a $4$-bit two's complement binary number is $\le-6$?

I am trying to figure out how I can turn this question into a Boolean function (which will then be turned into a boolean circuit). I know that $-6$ in $4$-bit two's complement is 1010 and I know the two's complements that are less than $-6,$ but I…
mdbej
  • 11
1
vote
1 answer

negation of the statement "Suman is brilliant and dishonest if and only if Suman is rich"

Consider the following statements $P$ : Suman is brilliant. $Q$ : Suman is rich. $R$ : Suman is honest. The negation of the statement, "Suman is brilliant and dishonest if and only if Suman is rich" can be equivalently expressed as (1) $\sim…
anonymous
  • 2,331
  • 14
  • 29