Introduction to Propositional and First-Order Logic

Propositional Logic

Simplest logic form using true or false statements.

Proposition

Declarative statement that is either true or false.

Tautology

Proposition formula that is always true.

Contradiction

Proposition formula that is always false.

Paradox

Proposition formula with both true and false values.

Atomic Proposition

Simple proposition consisting of a single symbol.

Compound Proposition

Combines atomic propositions using logical connectives.

Logical Connectives

Operators that connect propositions in logic.

First-Order Logic

Extension of propositional logic for knowledge representation.

Predicate Logic

Another name for first-order logic.

Syntax of FOL

Rules defining valid expressions in first-order logic.

Atomic Sentence

Basic sentence formed from a predicate and terms.

Complex Sentence

Combines atomic sentences using logical connectives.

Universal Quantifier

Indicates truth for all instances of a variable.

Existential Quantifier

Indicates truth for at least one instance.

Quantifiers

Specify the number of instances in logic.

Syntax of Propositional Logic

Defines allowable sentences for knowledge representation.

Logical Operators

Symbols that perform logical operations on propositions.

Knowledge Representation

Method of expressing information in logic form.

Logical Expression

Combination of propositions and connectives.

Properties of Quantifiers

Rules governing the behavior of quantifiers.

Subject in FOL

Main part of a statement in first-order logic.

Predicate in FOL

Relation that binds two atomic sentences.

Example of Tautology

Every student likes educative.

Example of Contradiction

All birds cannot fly.

Example of Paradox

Not all students like both Mathematics and Science.

Logical Notation

Symbolic representation of logical statements.

Natural Language Representation

Expressing statements in a concise logical form.

Predicate

Function defining relationships between variables.

Existential Quantifier (∃)

Indicates existence of at least one element.

Universal Quantifier (∀)

Indicates all elements satisfy a condition.

Negation (¬)

Logical operator indicating the opposite truth value.

Zero-Sum Game

One player's gain equals another's loss.

General-Sum Game

Players have independent utilities and outcomes.

Minimax Algorithm

Strategy minimizing maximum possible loss.

Alpha-Beta Pruning

Optimization technique reducing nodes evaluated in minimax.

Terminal State

Final state in a game with known utility.

Utility

Measure of preference or satisfaction in outcomes.

Game Tree

Graph representing possible moves in a game.

Depth-First Search (DFS)

Explores as far as possible along branches.

Breadth-First Search (BFS)

Explores all neighbors before moving deeper.

A* Search

Pathfinding algorithm using heuristics for efficiency.

Heuristic

Approximation used to guide search algorithms.

Monte Carlo Tree Search

Probabilistic method for decision-making in games.

Checkers

Board game with simple rules, solved in 2007.

Chess

Complex board game with significant AI advancements.

Go

Ancient board game, advanced AI achieved in 2016.

Game Formulation

Structure defining initial state, players, and actions.

Finite Lookahead

Limited foresight in decision-making processes.

Value of a State

Best achievable outcome from that state.

Adversarial Search

Search strategy considering opponent's possible moves.

Terminal-Test

Function determining if a game has ended.

Action

Move made by a player in a game.

Initial State (s0)

Starting configuration of a game.

Transition Model

Describes how actions change game states.

Team Games

Games where players collaborate for a common goal.

Admissible Heuristic

Heuristic h satisfies 0 ≤ h(n) ≤ h*(n).

True Cost

h*(n) represents actual cost to nearest goal.

Optimal Goal Node

Node A is the best goal in search.

Suboptimal Goal Node

Node B is not the best goal in search.

Expansion Order

A is expanded before B if h is admissible.

f-cost Definition

f(n) = g(n) + h(n) represents total cost.

Admissibility of h

Ensures f(n) ≤ g(A) for optimality.

g(A)

Cost from start to goal A.

Suboptimality of B

g(A) < g(B) indicates B is worse.

A* Tree Search

Optimal if heuristic is admissible.

Uniform-Cost Search (UCS)

Expands nodes equally in all directions.

Heuristic Design

Key to effective A* search performance.

8 Puzzle Heuristic

Count of misplaced tiles measures distance.

Manhattan Distance

Sum of horizontal and vertical distances.

Consistent Heuristic

Ensures f-values are non-decreasing.

Iterative Deepening A (IDA)

Uses f-limit instead of depth limit.

Recursive Best-First Search (RBFS)

Depth-first search with f-limit management.

Simplified Memory A (SMA)

Manages memory by dropping worst node.

Declarative Knowledge

Includes facts and concepts in sentences.

Procedural Knowledge

Knowledge of how to perform tasks.

Meta-Knowledge

Knowledge about other types of knowledge.

Cycle of Knowledge Representation

Components include perception, learning, and planning.

Logical Representation

Language with rules for unambiguous conclusions.

Semantic Network

Graph structure representing relationships between concepts.

Frame Representation

Record-like structure describing entities with attributes.

Production Rules

Condition-action pairs for problem-solving.

Recognize-Act Cycle

Process where conditions trigger actions.

Search Problem

Consists of state space, initial state, actions, and goals.

State Space

Set of all possible configurations in a problem.

Initial State

Starting configuration of the search problem.

Actions

Possible moves available in each state.

Goal Test

Determines if a state is a goal state.

Action Cost

Cost associated with taking an action.

Optimal Solution

Least cost action sequence to reach goal.

State Space Graph

Mathematical representation of a search problem.

Search Tree

Tree structure representing paths in state space.

Uniform Cost Search (UCS)

Expands nodes with lowest cumulative cost.

Iterative Deepening

Combines depth-first space efficiency with breadth-first completeness.

Complete Algorithm

Guaranteed to find a solution if one exists.

Optimal Algorithm

Guaranteed to find least cost path.

Time Complexity

Measure of time taken by an algorithm.

Space Complexity

Measure of memory used by an algorithm.

Agent

Entity that perceives and acts in an environment.

Planning Agent

Decides actions based on future evaluations.