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

how to make Propositional logic from several claims.

i'm having issues connecting the dots in order to create a main claim. if a sentence says, i will fly only if the plane arrived. let's say that $P =$ plane arrived, $Q =$ i will fly. so the sentence is $P\rightarrow Q ?$ thank you
0
votes
1 answer

Logical Connectives.

I have a statement. Every student at your school either can speak Russian or knows C++. Where P(x) is the statement "x can speak Russian". And Q(x) is the statement is the statement "x knows the computer language C++". I have to express this in…
0
votes
4 answers

Is the following logical statement answerable?

Children behave if they are not given candy. Angela is a child who is given candy. Therefore, Angela will misbehave. I don't think it's true nor false because there's not enough information given. I tried using modus tollens and got, If children…
0
votes
0 answers

Inferences, basic inference rules and substitution

Currently stuck on looking at some inferences to identify the basic inference rule of which it is a substitution instance. Examples and questions taken from book "Fuzzy set theory" by Klir/St Clair/Bo Yuan (which frustratingly does not contain the…
0
votes
1 answer

Proving $(B\to{\lnot}C)\to D$, ${\therefore}B\to({\lnot}C{\to}D)$

I'm teaching myself basic logic. I've answered all the other problems in the section, most rather easily, but this one. $$(B\to{\lnot}C)\to D\quad {\therefore}B\to({\lnot}C{\to}D)$$ original problem image (Note. The original version of this…
0
votes
1 answer

Please help with indetifying logical consequence.

Let's say that it is true that: a conclusion A is a logical consequence of a set of premises T iff negation of A is in T and T is not finitely performable. Formally written: (T ⊨ A) ⇔ T ⋃ {¬A} is not satisfiable. My question is the following: What…
TKN
  • 757
0
votes
1 answer

Using the statement "at most one" in propositional logic and in horns clause

I am studying for my exams and I am having some trouble understanding how to write the below statements in: Propositional logic Horn clause. A. Customer chooses Converse shoes B. Customer chooses Adidas shoes The customer can choose at most one…
Margue
  • 1
0
votes
2 answers

Can we change the premise by using the contrapositive?

Can we change the premise by using the contrapositive? For example, if we have $A \to (Q \land B)$. Say that $\neg (Q \land B) \to \neg A$, then start with the premise $\neg (Q \land B)$ and try to deduce $\neg A$.
0
votes
1 answer

Is $((A \wedge B) \rightarrow (C \wedge D))$ the same as $(A \wedge B \rightarrow C \wedge D)$?

I'm currently learning propositional logic and was wondering if I could rewrite the first statement as second (just less paranthesis)? Could it be interpreted as a totally different statement or it is fine as it is?
Fl1pp
  • 47
0
votes
2 answers

propositional logic syntax using different symbols

Is it possible for $A\Leftrightarrow B$ to be written using only $A,B,\sim,\vee$? If so, how?
GGG
  • 345
0
votes
1 answer

Examples of propositions without quantifiers to explain basic propositional logic?

To introduce the basics of logic, one ordinarily begins with propositional logic and then proceeds to predicate logic. Unfortunately, the examples of propositions typically either use "real-world sentences" (e.g., "George Washington lived in Mt.…
murray
  • 778
  • 3
  • 16
0
votes
1 answer

Difference between $\exists x ( f(x) \rightarrow g(x) )$ and $\exists x ( f(x) \land g(x) )$?

For converting english statements to logical statements, I've understood that $\forall$ uses $\rightarrow$ and $\exists$ uses $\land$ (generally). I referred a particular question on this site, but I lost track of it (apologies). Considering the…
0
votes
1 answer

Absorption's Law - Negative proposition affects the law?

This is a simple question. It's known that the absorption's law is like the following example: p ∧ (p V q) = p But, if the proposition has a negation, does this affect the law? for example: p ∧ ¬(p V q) = p Is this correct? Edit: Is the De…
user688279
0
votes
3 answers

De Morgan's Law - The answer is with square brackets or without square brackets?

De Morgan's Law - Propositional Calculus Can someone tell me what's the correct way to solve this proposition with De Morgan's Law? Proposition: $q \vee ¬[ (p \wedge q) \vee ¬q ]$ [Answers] Option 1: $q \vee ¬(p \wedge q) \wedge q$ Option 2: $q…
user688279
0
votes
1 answer

Is it possible to transform a propositional logic formula so that every propositions appear only once?

I'm trying to compare two formulae to see which one is easier to satisfy and I thought that comparing how many models they have would be a good way to do so. From what I've seen and read, it seems harder to count the number of models when a…
Florian
  • 21