Questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions would fit very nicely under this tag. Questions about other kind of logics should be tagged with [logic] instead.

learn more… | top users | synonyms (1)

2
votes
0answers
16 views

Can an equation be shown to be valid through logic over an continuous range?

I may be asking the impossible - but would appreciate it if someone else were to confirm this for me, rather than me just thinking this... I have a black box function, $f(x)$ that I don't know ...
2
votes
1answer
26 views

How does one go from this step: $(\neg p \lor \neg q) \lor (p \lor q)$ to this one: $(\neg p \lor p) \lor (\neg q \lor q)$

I'm reviewing discrete math a second time (after it being over a decade since I took the course in college). How does one go from this step: $(\neg p \lor \neg q) \lor (p \lor q)$ to this one: $(\neg ...
0
votes
1answer
33 views

First Order Logic Question

$\forall x\ \forall y\ P(x,y) \to \forall x\ \forall y\ P(y,x)$ Is this a tautology? Is there a set method that we can use to find whether a wff is a tautology?
0
votes
2answers
48 views

Solving Logical equivalence & propositional logic problems without truth tables

I have no particular "Logic question" in hand at the time being, but need help to understand a way that can be used to prove "Logical equivalence without using truth tables". moreover can we solve ...
0
votes
2answers
35 views

Solve it by using logical proposition

Show that given logical proposition is tautology $((A \implies C) \land (B \implies C) \land \lnot C) \implies \lnot (A \lor B) $ I can apply the implication rule first and got $\lnot((A \implies ...
2
votes
1answer
34 views

How Do You Show That There Exist Infinitely Many Organic Tautologies?

This question takes inspiration from this question. A tautology is organic if none of it's proper sub-formulas are tautologies. In other words, if all of the sub-formulas excluding the formula ...
0
votes
0answers
10 views

Basic Predicate & Quantifier Doubt

Which one of the following well formed formulae is tautology? (A)∀x∃yR(x,y)<=>∃y∀xR(x,y) (B)(∀x[∃yR(x,y)=>S(x,y)])=>∀x∃yS(x,y) (C)[(∀x∃y(p(x,y)=>R(x,y))]=>[∀x∃y(¬p(x,y) V R(x,y)] ...
0
votes
1answer
39 views

Proof of formulas in sequent calculus

Is there an algorithm for proof of formulas in sequent calculus, like resolution method? I'm especially interested in natural deduction. UPDATE Well, we have one scheme of axioms $$\Phi\vdash\Phi$$ ...
2
votes
1answer
41 views

Can we see natural deduction rules as functions or even as formal grammars?

Is there a way of seeing natural deduction rules as functions or even as formal grammars, maybe context-free grammars or Lambek grammars? It seems quite "easy" to see the rules as functions which take ...
0
votes
2answers
58 views

Prove $(p \rightarrow q) \land (r \rightarrow s) \implies ( \neg p \lor \neg r \lor q \lor s)$

$$((p \rightarrow q) \land (r \rightarrow s))\rightarrow ((p\land r)\rightarrow (q\lor s))$$ I have some problem with formula: $$(p \rightarrow q) \land (r \rightarrow s) $$ $$\equiv(\neg p \lor q) ...
2
votes
1answer
33 views

If $\Sigma$ is finitely satisfiable, can both $\Sigma \cup \{ \phi\}$ and $\Sigma \cup \{ \neg \phi\}$ be finitely satisfiable?

In propositional logic, if $\Sigma$ is finitely satisfiable, can both $\Sigma \cup \{ \phi\}$ and $\Sigma \cup \{ \neg \phi\}$ be finitely satisfiable? I proved that at least one of $\Sigma \cup \{ ...
2
votes
3answers
47 views

Logical Equivalence

Prove that p $\rightarrow$(q$\rightarrow$p) is logically equivalent to $\neg p$ $\rightarrow$(p$\rightarrow$q) without using truth table. It is easy to show that both the statements are tautologies. ...
0
votes
1answer
19 views

Is $ R = \{ (A,B) \in \Omega² \quad| \quad A \land B \} \quad$ with $\Omega = \{ A\quad| $ A is a proposition $ \}$ reflexive?

Is $ R = \{ (A,B) \in \Omega² \quad| \quad A \land B \} \quad$ with $\Omega = \{ A\quad| $ A is a proposition $ \}$ reflexive? I assume that you have to consider untrue propositions, too. $A \land ...
1
vote
0answers
22 views

Does a Length Always Exist such that a Tautology Always Exists Beyond That Length?

Suppose we have some set of fixed connectives such that tautologies exist and we write everything in Polish notation. The length of a WFF consists of the number of symbols that it has. WFFs can get ...
-1
votes
2answers
31 views

Finding a morphism from one boolean expression to another i.e. $\phi :(x \Rightarrow y) \rightarrow (y \vee z)$

What I would like to do is figure out how to get from $(x \Rightarrow y) $ to $ (y \vee z)$, that what I could AND or OR to $(x \Rightarrow y) $ so as to give $ (y \vee z)$. Breaking this down I ...
1
vote
1answer
15 views

Constructing a tautology given a set $\Sigma \subset $Prop(A) with special properties.

I am trying to follow Logic Notes of Lou Van Dries and I am stuck at a particular question in propositional logic. Assuming $A$ is any set and Prop$(A)$ is the set of propositions on $A$. The ...
-3
votes
4answers
77 views

Prove that $(\neg p \wedge \neg q) \vee (p \wedge q) \equiv (\neg p \vee q) \wedge (\neg q \vee p)$ [closed]

Prove that $(\neg p \wedge \neg q) \vee (p \wedge q) \equiv (\neg p \vee q) \wedge (\neg q \vee p)$. I need to prove it by using equivalent sentences.
1
vote
1answer
34 views

Logic normals forms, wolfram, problem.

This is formula which I must write as CNF, DNF and Negation of formula as CNF and DNF: $$(p \rightarrow (q \rightarrow r)) \rightarrow ((p \rightarrow \neg r) \rightarrow (p \rightarrow \neg q))$$ ...
1
vote
3answers
43 views

When I can reverse the logical operators?

I heard say that is logically equivalent to say it: $$\neg (p \vee q) = p \land q$$ So every time you have a negation operator in front can make a "distributive" altering the operator from within? ...
0
votes
1answer
27 views

Logical implications in classic logic

I have the following problem: If Joseph is playing piano or Joaquim is playing guitar, then John is not sleeping. I perfectly understood the situation but didn't understand the second row of ...
1
vote
0answers
26 views

Proving strong completeness of propositional logic by assuming weak completeness via algebraic methods.

In logic via algebra (page $93$), Halmos tries to prove strong completeness ( if $S\models q$ then $S\vdash q$) assuming weak completeness ( if $q$ is a valid in the Boolean logic $(A,F)$ then $q\in ...
2
votes
1answer
49 views

Universal quantifier question: $(\forall x)[x < 0 \Rightarrow x^2 > 0]$

Universal quantifier question: $(\forall x)[x < 0 \Rightarrow x^2 > 0]$. Given the above expression, For all of $x$ [ if $x$ is less than zero, then $x^2$ is greater than zero]. Is that a ...
1
vote
1answer
39 views

Find the murderer by using truth table for formal logic (formal disjunction or formal implication)

I'm studying formal logic and i was wondering if you can check whether I've solved this task correctly. TASK. Two people are arrested as suspects for a murder case, Stan and Peter. Four witnesses ...
1
vote
3answers
60 views

is this proposition (inference) valid?

Is this inference valid or invalid? Why and how to prove this kind of question? $$p \rightarrow q, \neg q \rightarrow r , r \vDash p $$ Would a single truth table be enough for all types?
0
votes
1answer
27 views

Disjunction Elimination Proof

P∨(Q∨R) ⊢ Q∨(P∨R) Proof: 1.) P∨(Q∨R) Assumption 2.) P Assumption 3.) P∨R 2.) Disjunction Introduction 4.) Q∨(P∨R) 3.) Disjunction Introduction 5.) Q∨R Assumption 6.) Q ...
8
votes
4answers
683 views

Is the following a valid mathematical statement?

For all $f:\mathbb N\to\{1,2,3,\ldots,100\}$, If $f$ is a one to one correspondence, Then $f^{-1}(2)=3$ It seems as though this should not be a valid statement, since the implication fails to ...
12
votes
1answer
171 views

Representing predicate logic as arithmetic

Summary Since the below is quite long, I thought I'd add this summary. Given the following: A statement in proposition logic can be converted to an arithmetic expression over the integers modulo ...
2
votes
2answers
71 views

Difference between Logical Axioms and Rules of Inference

What's the difference between Logical Axioms and Rules of Inference? In my understanding, both are ordered pairs of formulas which are used to reach a conclusion through syllogisms. My questions ...
5
votes
3answers
56 views

Difference between Gentzen and Hilbert Calculi

What is the difference between Gentzen and Hilbert Calculi? From my understanding from the reading of Rautenberg's Concise Introduction to Mathematical Logic, Gentzen calculus is based on sequents ...
0
votes
2answers
20 views

Substitutions as mappings from the set of Propositional Variables to the set of Formulas

Rautenberg defines substitutions in propositional calculus as follows: " A (propositional) substitution is a mapping σ : PV →F that is extended in a natural way to a mapping σ : F → F " PV: set of ...
1
vote
1answer
44 views

Are there any consistency proofs for propositional or first-order logic?

Take for example the Hilbert-style axiomatizations of the propositional and first-order calculus. Since a crucial point when operating with a proof system is that no contradictions must be found in ...
0
votes
1answer
14 views

Epress $\exists! x P(x)$using universal quantifications, existential quantifications and logical operators

Epress the quantification $\exists! x P(x)$, using universal quantifications, existential quantifications and logical operators. Does anyone have an idea?
3
votes
1answer
55 views

No truth function that is expressed by a formula that uses only implication and equivalence connectives

I proved the following statement by induction: Let $A$ be a propositional formula which uses only the connectives $→$ and $↔$. Prove (by induction on the complexity of $A$) that if every ...
-1
votes
1answer
36 views

Difference between DNF and CNF

I'm stuck on a particular question, about Propositional Logic. Let $A$ be the propositional formula $((\lnot p \rightarrow q) \leftrightarrow\ (\lnot q \rightarrow \lnot r))$. Find a propositional ...
0
votes
2answers
72 views

Prove propositional logic by resolution.

Prove $$[(p→q) \wedge (qr→s)]\to [pr→s],$$ which is the same as $$[(\lnot p\lor q) \wedge (\lnot (qr) \lor s)]\to [\lnot (pr) \lor s]$$ I believe it can just be done with algebra rules, but I got ...
2
votes
1answer
57 views

Lindenbaum-Theorem only concerning sentential logic provable in ZF?

Is the Lindenbaum-Theorem of sentential logic (= propositional logic) provable in ZF (i. e. without the axiom of choice)? Lindenbaum's theorem of sentential logic states that every set $\Sigma$ of ...
1
vote
1answer
43 views

Proving by induction on the length of a propositional formula?

I'm having a little trouble understanding the following proof question because I'm unsure what defines the 'length' of a propositional formula, I've seen multiple definitions whether it's the number ...
1
vote
1answer
18 views

Writing in disjunctive normal form using logical laws

I'm having trouble converting the below formula to disjunctive normal form using logical laws. I found the DNF using truth tables but I am having issues using just logical laws. Here is the formula: ...
1
vote
1answer
42 views

$(Ǝx)H(x) \dashv \vdash (Ǝy)H(y)$?

I can prove the statement using the natural deduction, but I keep getting confused about this sequent, so it would be very thankful if someone can help me to understand this concept of predicate ...
0
votes
0answers
35 views

Finding a truth function

I wanted to find a truth function $f$ if it exists that make the formula below true: $((p\to \lnot(q \oplus \lnot p)) \to (\lnot r \oplus (q \to p)))$ Where the $\oplus$ operator is defined as: ...
1
vote
3answers
33 views

Showing tautology without a truth table.

Show that the conditional statement is a tautology without using a truth table. $a)$ $(p \wedge q) \rightarrow p$ My suggestion would be getting rid of the implication first, so $(p \wedge q) ...
0
votes
0answers
21 views

Some computations in propositional calculus

I have some expressions of the form. I want to express them as $\bigvee (\bigwedge v_i)$. These are: 1) $(v_1 \vee v_2) \wedge (v_3 \vee v_4 \vee v_5)$ 2) $(v_1 \vee v_2) \wedge (v_1 \vee v_3)$ 3) ...
1
vote
2answers
24 views

Natural deduction proof for : p → ( c ∨ b) , b → s ⊢ ( p ∧ ¬s)→ c

I am trying to prove the following statement but I am getting stuck at the 6th line and I'm unsure how to continue. p → ( c ∨ b) , b → s ⊢ ( p ∧ ¬s)→ c p → ( c ∨ b) (premise) b → s (premise) ...
0
votes
3answers
58 views

Proving $(p \oplus q) \oplus r=p \oplus (q \oplus r)$

I was assigned to prove the associative law on xor. $(p \oplus q) \oplus r=p \oplus (q \oplus r)$ I'm sure $(p\oplus q)=(p∧¬q)∨(¬p∧q)$ But I got stuck on $(p \oplus q) \oplus ...
2
votes
1answer
47 views

Creating a proposition from a truth table using only ~ ⋀ and v

I have to find a simple expression for the third column in the truth table using only the logical connectives I've mention above. There are two questions that are involved here. Problem 1: Truth ...
1
vote
0answers
33 views

Construct theory with a condition

I would need some help here. I'm preparing for finals from mathematical logic and as I am browsing through some exercises, I often found these types: Let's say we have 2 propositions $\phi$ and ...
1
vote
1answer
21 views

Can you give a simple CDCL example?

I am trying to understand how Conflict-Driven Clause Learning works. After reading through the lecture slides, wikipedia article and some additional slides I found online I realized that I still can't ...
1
vote
2answers
25 views

Can I use De Morgan's law in the third step as shown below to solve this problem?

$(p \rightarrow q) \wedge (\neg p \rightarrow q)$ $\equiv(p \rightarrow q) \wedge (\neg p \rightarrow q)$ $\equiv(\neg p \vee q) \wedge (p \vee q)$ $\equiv \neg(\neg (\neg p \vee q) \vee \neg(p ...
3
votes
1answer
45 views

Simplifying propositional logic

Hi I asked a question a few hours ago which has been solved but I got stuck on another exercise so I thought I'd reach out for some help. I have the premise: $((A \to B) \land (\lnot A \to C))$ ...
1
vote
1answer
33 views

How can i prove $p\to (q \vee r) \equiv (p \wedge \sim q) \to r$?

please Help me in this question i have tried to solve it like this: $$p \to (q \vee r) \equiv (p \wedge \sim q)\to r$$ $$p \vee \sim (q \vee r) \equiv \sim(p \wedge q)\vee r$$ $$p \vee \sim q \wedge ...